c1_ValueMap.cpp revision 1472:c18cbe5936b8
1/* 2 * Copyright (c) 1999, 2005, 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 * 23 */ 24 25#include "incls/_precompiled.incl" 26#include "incls/_c1_ValueMap.cpp.incl" 27 28 29#ifndef PRODUCT 30 31 int ValueMap::_number_of_finds = 0; 32 int ValueMap::_number_of_hits = 0; 33 int ValueMap::_number_of_kills = 0; 34 35 #define TRACE_VALUE_NUMBERING(code) if (PrintValueNumbering) { code; } 36 37#else 38 39 #define TRACE_VALUE_NUMBERING(code) 40 41#endif 42 43 44ValueMap::ValueMap() 45 : _nesting(0) 46 , _entries(ValueMapInitialSize, NULL) 47 , _killed_values() 48 , _entry_count(0) 49{ 50 NOT_PRODUCT(reset_statistics()); 51} 52 53 54ValueMap::ValueMap(ValueMap* old) 55 : _nesting(old->_nesting + 1) 56 , _entries(old->_entries.length()) 57 , _killed_values() 58 , _entry_count(old->_entry_count) 59{ 60 for (int i = size() - 1; i >= 0; i--) { 61 _entries.at_put(i, old->entry_at(i)); 62 } 63 _killed_values.set_from(&old->_killed_values); 64} 65 66 67void ValueMap::increase_table_size() { 68 int old_size = size(); 69 int new_size = old_size * 2 + 1; 70 71 ValueMapEntryList worklist(8); 72 ValueMapEntryArray new_entries(new_size, NULL); 73 int new_entry_count = 0; 74 75 TRACE_VALUE_NUMBERING(tty->print_cr("increasing table size from %d to %d", old_size, new_size)); 76 77 for (int i = old_size - 1; i >= 0; i--) { 78 ValueMapEntry* entry; 79 for (entry = entry_at(i); entry != NULL; entry = entry->next()) { 80 if (!is_killed(entry->value())) { 81 worklist.push(entry); 82 } 83 } 84 85 while (!worklist.is_empty()) { 86 entry = worklist.pop(); 87 int new_index = entry_index(entry->hash(), new_size); 88 89 if (entry->nesting() != nesting() && new_entries.at(new_index) != entry->next()) { 90 // changing entries with a lower nesting than the current nesting of the table 91 // is not allowed because then the same entry is contained in multiple value maps. 92 // clone entry when next-pointer must be changed 93 entry = new ValueMapEntry(entry->hash(), entry->value(), entry->nesting(), NULL); 94 } 95 entry->set_next(new_entries.at(new_index)); 96 new_entries.at_put(new_index, entry); 97 new_entry_count++; 98 } 99 } 100 101 _entries = new_entries; 102 _entry_count = new_entry_count; 103} 104 105 106Value ValueMap::find_insert(Value x) { 107 const intx hash = x->hash(); 108 if (hash != 0) { 109 // 0 hash means: exclude from value numbering 110 NOT_PRODUCT(_number_of_finds++); 111 112 for (ValueMapEntry* entry = entry_at(entry_index(hash, size())); entry != NULL; entry = entry->next()) { 113 if (entry->hash() == hash) { 114 Value f = entry->value(); 115 116 if (!is_killed(f) && f->is_equal(x)) { 117 NOT_PRODUCT(_number_of_hits++); 118 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())); 119 120 if (entry->nesting() != nesting() && f->as_Constant() == NULL) { 121 // non-constant values of of another block must be pinned, 122 // otherwise it is possible that they are not evaluated 123 f->pin(Instruction::PinGlobalValueNumbering); 124 } 125 126 return f; 127 128 } 129 } 130 } 131 132 // x not found, so insert it 133 if (entry_count() >= size_threshold()) { 134 increase_table_size(); 135 } 136 int idx = entry_index(hash, size()); 137 _entries.at_put(idx, new ValueMapEntry(hash, x, nesting(), entry_at(idx))); 138 _entry_count++; 139 140 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())); 141 } 142 143 return x; 144} 145 146 147#define GENERIC_KILL_VALUE(must_kill_implementation) \ 148 NOT_PRODUCT(_number_of_kills++); \ 149 \ 150 for (int i = size() - 1; i >= 0; i--) { \ 151 ValueMapEntry* prev_entry = NULL; \ 152 for (ValueMapEntry* entry = entry_at(i); entry != NULL; entry = entry->next()) { \ 153 Value value = entry->value(); \ 154 \ 155 must_kill_implementation(must_kill, entry, value) \ 156 \ 157 if (must_kill) { \ 158 kill_value(value); \ 159 \ 160 if (prev_entry == NULL) { \ 161 _entries.at_put(i, entry->next()); \ 162 _entry_count--; \ 163 } else if (prev_entry->nesting() == nesting()) { \ 164 prev_entry->set_next(entry->next()); \ 165 _entry_count--; \ 166 } else { \ 167 prev_entry = entry; \ 168 } \ 169 \ 170 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())); \ 171 } else { \ 172 prev_entry = entry; \ 173 } \ 174 } \ 175 } \ 176 177#define MUST_KILL_MEMORY(must_kill, entry, value) \ 178 bool must_kill = value->as_LoadField() != NULL || value->as_LoadIndexed() != NULL; 179 180#define MUST_KILL_ARRAY(must_kill, entry, value) \ 181 bool must_kill = value->as_LoadIndexed() != NULL \ 182 && value->type()->tag() == type->tag(); 183 184#define MUST_KILL_FIELD(must_kill, entry, value) \ 185 /* ciField's are not unique; must compare their contents */ \ 186 LoadField* lf = value->as_LoadField(); \ 187 bool must_kill = lf != NULL \ 188 && lf->field()->holder() == field->holder() \ 189 && lf->field()->offset() == field->offset(); 190 191#define MUST_KILL_EXCEPTION(must_kill, entry, value) \ 192 assert(entry->nesting() < nesting(), "must not find bigger nesting than current"); \ 193 bool must_kill = (entry->nesting() == nesting() - 1); 194 195 196void ValueMap::kill_memory() { 197 GENERIC_KILL_VALUE(MUST_KILL_MEMORY); 198} 199 200void ValueMap::kill_array(ValueType* type) { 201 GENERIC_KILL_VALUE(MUST_KILL_ARRAY); 202} 203 204void ValueMap::kill_field(ciField* field) { 205 GENERIC_KILL_VALUE(MUST_KILL_FIELD); 206} 207 208void ValueMap::kill_exception() { 209 GENERIC_KILL_VALUE(MUST_KILL_EXCEPTION); 210} 211 212 213void ValueMap::kill_map(ValueMap* map) { 214 assert(is_global_value_numbering(), "only for global value numbering"); 215 _killed_values.set_union(&map->_killed_values); 216} 217 218void ValueMap::kill_all() { 219 assert(is_local_value_numbering(), "only for local value numbering"); 220 for (int i = size() - 1; i >= 0; i--) { 221 _entries.at_put(i, NULL); 222 } 223 _entry_count = 0; 224} 225 226 227#ifndef PRODUCT 228 229void ValueMap::print() { 230 tty->print_cr("(size %d, entries %d, nesting %d)", size(), entry_count(), nesting()); 231 232 int entries = 0; 233 for (int i = 0; i < size(); i++) { 234 if (entry_at(i) != NULL) { 235 tty->print(" %2d: ", i); 236 for (ValueMapEntry* entry = entry_at(i); entry != NULL; entry = entry->next()) { 237 Value value = entry->value(); 238 tty->print("%s %c%d (%s%d) -> ", value->name(), value->type()->tchar(), value->id(), is_killed(value) ? "x" : "", entry->nesting()); 239 entries++; 240 } 241 tty->print_cr("NULL"); 242 } 243 } 244 245 _killed_values.print(); 246 assert(entry_count() == entries, "entry_count incorrect"); 247} 248 249void ValueMap::reset_statistics() { 250 _number_of_finds = 0; 251 _number_of_hits = 0; 252 _number_of_kills = 0; 253} 254 255void ValueMap::print_statistics() { 256 float hit_rate = 0; 257 if (_number_of_finds != 0) { 258 hit_rate = (float)_number_of_hits / _number_of_finds; 259 } 260 261 tty->print_cr("finds:%3d hits:%3d kills:%3d hit rate: %1.4f", _number_of_finds, _number_of_hits, _number_of_kills, hit_rate); 262} 263 264#endif 265 266 267 268class ShortLoopOptimizer : public ValueNumberingVisitor { 269 private: 270 GlobalValueNumbering* _gvn; 271 BlockList _loop_blocks; 272 bool _too_complicated_loop; 273 274 // simplified access to methods of GlobalValueNumbering 275 ValueMap* current_map() { return _gvn->current_map(); } 276 ValueMap* value_map_of(BlockBegin* block) { return _gvn->value_map_of(block); } 277 278 // implementation for abstract methods of ValueNumberingVisitor 279 void kill_memory() { _too_complicated_loop = true; } 280 void kill_field(ciField* field) { current_map()->kill_field(field); }; 281 void kill_array(ValueType* type) { current_map()->kill_array(type); }; 282 283 public: 284 ShortLoopOptimizer(GlobalValueNumbering* gvn) 285 : _gvn(gvn) 286 , _loop_blocks(ValueMapMaxLoopSize) 287 , _too_complicated_loop(false) 288 { 289 } 290 291 bool process(BlockBegin* loop_header); 292}; 293 294 295bool ShortLoopOptimizer::process(BlockBegin* loop_header) { 296 TRACE_VALUE_NUMBERING(tty->print_cr("** loop header block")); 297 298 _too_complicated_loop = false; 299 _loop_blocks.clear(); 300 _loop_blocks.append(loop_header); 301 302 for (int i = 0; i < _loop_blocks.length(); i++) { 303 BlockBegin* block = _loop_blocks.at(i); 304 TRACE_VALUE_NUMBERING(tty->print_cr("processing loop block B%d", block->block_id())); 305 306 if (block->is_set(BlockBegin::exception_entry_flag)) { 307 // this would be too complicated 308 return false; 309 } 310 311 // add predecessors to worklist 312 for (int j = block->number_of_preds() - 1; j >= 0; j--) { 313 BlockBegin* pred = block->pred_at(j); 314 315 ValueMap* pred_map = value_map_of(pred); 316 if (pred_map != NULL) { 317 current_map()->kill_map(pred_map); 318 } else if (!_loop_blocks.contains(pred)) { 319 if (_loop_blocks.length() >= ValueMapMaxLoopSize) { 320 return false; 321 } 322 _loop_blocks.append(pred); 323 } 324 } 325 326 // use the instruction visitor for killing values 327 for (Value instr = block->next(); instr != NULL; instr = instr->next()) { 328 instr->visit(this); 329 if (_too_complicated_loop) { 330 return false; 331 } 332 } 333 } 334 335 TRACE_VALUE_NUMBERING(tty->print_cr("** loop successfully optimized")); 336 return true; 337} 338 339 340GlobalValueNumbering::GlobalValueNumbering(IR* ir) 341 : _current_map(NULL) 342 , _value_maps(ir->linear_scan_order()->length(), NULL) 343{ 344 TRACE_VALUE_NUMBERING(tty->print_cr("****** start of global value numbering")); 345 346 ShortLoopOptimizer short_loop_optimizer(this); 347 int subst_count = 0; 348 349 BlockList* blocks = ir->linear_scan_order(); 350 int num_blocks = blocks->length(); 351 352 BlockBegin* start_block = blocks->at(0); 353 assert(start_block == ir->start() && start_block->number_of_preds() == 0 && start_block->dominator() == NULL, "must be start block"); 354 assert(start_block->next()->as_Base() != NULL && start_block->next()->next() == NULL, "start block must not have instructions"); 355 356 // initial, empty value map with nesting 0 357 set_value_map_of(start_block, new ValueMap()); 358 359 for (int i = 1; i < num_blocks; i++) { 360 BlockBegin* block = blocks->at(i); 361 TRACE_VALUE_NUMBERING(tty->print_cr("**** processing block B%d", block->block_id())); 362 363 int num_preds = block->number_of_preds(); 364 assert(num_preds > 0, "block must have predecessors"); 365 366 BlockBegin* dominator = block->dominator(); 367 assert(dominator != NULL, "dominator must exist"); 368 assert(value_map_of(dominator) != NULL, "value map of dominator must exist"); 369 370 // create new value map with increased nesting 371 _current_map = new ValueMap(value_map_of(dominator)); 372 373 if (num_preds == 1) { 374 assert(dominator == block->pred_at(0), "dominator must be equal to predecessor"); 375 // nothing to do here 376 377 } else if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) { 378 // block has incoming backward branches -> try to optimize short loops 379 if (!short_loop_optimizer.process(block)) { 380 // loop is too complicated, so kill all memory loads because there might be 381 // stores to them in the loop 382 current_map()->kill_memory(); 383 } 384 385 } else { 386 // only incoming forward branches that are already processed 387 for (int j = 0; j < num_preds; j++) { 388 BlockBegin* pred = block->pred_at(j); 389 ValueMap* pred_map = value_map_of(pred); 390 391 if (pred_map != NULL) { 392 // propagate killed values of the predecessor to this block 393 current_map()->kill_map(value_map_of(pred)); 394 } else { 395 // kill all memory loads because predecessor not yet processed 396 // (this can happen with non-natural loops and OSR-compiles) 397 current_map()->kill_memory(); 398 } 399 } 400 } 401 402 if (block->is_set(BlockBegin::exception_entry_flag)) { 403 current_map()->kill_exception(); 404 } 405 406 TRACE_VALUE_NUMBERING(tty->print("value map before processing block: "); current_map()->print()); 407 408 // visit all instructions of this block 409 for (Value instr = block->next(); instr != NULL; instr = instr->next()) { 410 assert(!instr->has_subst(), "substitution already set"); 411 412 // check if instruction kills any values 413 instr->visit(this); 414 415 if (instr->hash() != 0) { 416 Value f = current_map()->find_insert(instr); 417 if (f != instr) { 418 assert(!f->has_subst(), "can't have a substitution"); 419 instr->set_subst(f); 420 subst_count++; 421 } 422 } 423 } 424 425 // remember value map for successors 426 set_value_map_of(block, current_map()); 427 } 428 429 if (subst_count != 0) { 430 SubstitutionResolver resolver(ir); 431 } 432 433 TRACE_VALUE_NUMBERING(tty->print("****** end of global value numbering. "); ValueMap::print_statistics()); 434} 435