1 /* 2 * Copyright (c) 1999, 2010, 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 "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" 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 }