Mercurial > hg > truffle
comparison src/share/vm/c1/c1_ValueMap.cpp @ 8860:46f6f063b272
7153771: array bound check elimination for c1
Summary: when possible optimize out array bound checks, inserting predicates when needed.
Reviewed-by: never, kvn, twisti
Contributed-by: thomaswue <thomas.wuerthinger@oracle.com>
author | roland |
---|---|
date | Thu, 21 Mar 2013 09:27:54 +0100 |
parents | b9a9ed0f8eeb |
children | 84ab5667f290 |
comparison
equal
deleted
inserted
replaced
8780:98f3af397705 | 8860:46f6f063b272 |
---|---|
24 | 24 |
25 #include "precompiled.hpp" | 25 #include "precompiled.hpp" |
26 #include "c1/c1_Canonicalizer.hpp" | 26 #include "c1/c1_Canonicalizer.hpp" |
27 #include "c1/c1_IR.hpp" | 27 #include "c1/c1_IR.hpp" |
28 #include "c1/c1_ValueMap.hpp" | 28 #include "c1/c1_ValueMap.hpp" |
29 #include "c1/c1_ValueStack.hpp" | |
29 #include "utilities/bitMap.inline.hpp" | 30 #include "utilities/bitMap.inline.hpp" |
30 | |
31 | 31 |
32 #ifndef PRODUCT | 32 #ifndef PRODUCT |
33 | 33 |
34 int ValueMap::_number_of_finds = 0; | 34 int ValueMap::_number_of_finds = 0; |
35 int ValueMap::_number_of_hits = 0; | 35 int ValueMap::_number_of_hits = 0; |
190 LoadField* lf = value->as_LoadField(); \ | 190 LoadField* lf = value->as_LoadField(); \ |
191 bool must_kill = lf != NULL \ | 191 bool must_kill = lf != NULL \ |
192 && lf->field()->holder() == field->holder() \ | 192 && lf->field()->holder() == field->holder() \ |
193 && (all_offsets || lf->field()->offset() == field->offset()); | 193 && (all_offsets || lf->field()->offset() == field->offset()); |
194 | 194 |
195 #define MUST_KILL_EXCEPTION(must_kill, entry, value) \ | |
196 assert(entry->nesting() < nesting(), "must not find bigger nesting than current"); \ | |
197 bool must_kill = (entry->nesting() == nesting() - 1); | |
198 | |
199 | 195 |
200 void ValueMap::kill_memory() { | 196 void ValueMap::kill_memory() { |
201 GENERIC_KILL_VALUE(MUST_KILL_MEMORY); | 197 GENERIC_KILL_VALUE(MUST_KILL_MEMORY); |
202 } | 198 } |
203 | 199 |
206 } | 202 } |
207 | 203 |
208 void ValueMap::kill_field(ciField* field, bool all_offsets) { | 204 void ValueMap::kill_field(ciField* field, bool all_offsets) { |
209 GENERIC_KILL_VALUE(MUST_KILL_FIELD); | 205 GENERIC_KILL_VALUE(MUST_KILL_FIELD); |
210 } | 206 } |
211 | |
212 void ValueMap::kill_exception() { | |
213 GENERIC_KILL_VALUE(MUST_KILL_EXCEPTION); | |
214 } | |
215 | |
216 | 207 |
217 void ValueMap::kill_map(ValueMap* map) { | 208 void ValueMap::kill_map(ValueMap* map) { |
218 assert(is_global_value_numbering(), "only for global value numbering"); | 209 assert(is_global_value_numbering(), "only for global value numbering"); |
219 _killed_values.set_union(&map->_killed_values); | 210 _killed_values.set_union(&map->_killed_values); |
220 } | 211 } |
272 class ShortLoopOptimizer : public ValueNumberingVisitor { | 263 class ShortLoopOptimizer : public ValueNumberingVisitor { |
273 private: | 264 private: |
274 GlobalValueNumbering* _gvn; | 265 GlobalValueNumbering* _gvn; |
275 BlockList _loop_blocks; | 266 BlockList _loop_blocks; |
276 bool _too_complicated_loop; | 267 bool _too_complicated_loop; |
268 bool _has_field_store[T_ARRAY + 1]; | |
269 bool _has_indexed_store[T_ARRAY + 1]; | |
277 | 270 |
278 // simplified access to methods of GlobalValueNumbering | 271 // simplified access to methods of GlobalValueNumbering |
279 ValueMap* current_map() { return _gvn->current_map(); } | 272 ValueMap* current_map() { return _gvn->current_map(); } |
280 ValueMap* value_map_of(BlockBegin* block) { return _gvn->value_map_of(block); } | 273 ValueMap* value_map_of(BlockBegin* block) { return _gvn->value_map_of(block); } |
281 | 274 |
282 // implementation for abstract methods of ValueNumberingVisitor | 275 // implementation for abstract methods of ValueNumberingVisitor |
283 void kill_memory() { _too_complicated_loop = true; } | 276 void kill_memory() { _too_complicated_loop = true; } |
284 void kill_field(ciField* field, bool all_offsets) { current_map()->kill_field(field, all_offsets); }; | 277 void kill_field(ciField* field, bool all_offsets) { |
285 void kill_array(ValueType* type) { current_map()->kill_array(type); }; | 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 } | |
286 | 287 |
287 public: | 288 public: |
288 ShortLoopOptimizer(GlobalValueNumbering* gvn) | 289 ShortLoopOptimizer(GlobalValueNumbering* gvn) |
289 : _gvn(gvn) | 290 : _gvn(gvn) |
290 , _loop_blocks(ValueMapMaxLoopSize) | 291 , _loop_blocks(ValueMapMaxLoopSize) |
291 , _too_complicated_loop(false) | 292 , _too_complicated_loop(false) |
292 { | 293 { |
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]; | |
293 } | 308 } |
294 | 309 |
295 bool process(BlockBegin* loop_header); | 310 bool process(BlockBegin* loop_header); |
296 }; | 311 }; |
297 | 312 |
313 class LoopInvariantCodeMotion : public StackObj { | |
314 private: | |
315 GlobalValueNumbering* _gvn; | |
316 ShortLoopOptimizer* _short_loop_optimizer; | |
317 Instruction* _insertion_point; | |
318 ValueStack * _state; | |
319 | |
320 void set_invariant(Value v) const { _gvn->set_processed(v); } | |
321 bool is_invariant(Value v) const { return _gvn->is_processed(v); } | |
322 | |
323 void process_block(BlockBegin* block); | |
324 | |
325 public: | |
326 LoopInvariantCodeMotion(ShortLoopOptimizer *slo, GlobalValueNumbering* gvn, BlockBegin* loop_header, BlockList* loop_blocks); | |
327 }; | |
328 | |
329 LoopInvariantCodeMotion::LoopInvariantCodeMotion(ShortLoopOptimizer *slo, GlobalValueNumbering* gvn, BlockBegin* loop_header, BlockList* loop_blocks) | |
330 : _gvn(gvn), _short_loop_optimizer(slo) { | |
331 | |
332 TRACE_VALUE_NUMBERING(tty->print_cr("using loop invariant code motion loop_header = %d", loop_header->block_id())); | |
333 TRACE_VALUE_NUMBERING(tty->print_cr("** loop invariant code motion for short loop B%d", loop_header->block_id())); | |
334 | |
335 BlockBegin* insertion_block = loop_header->dominator(); | |
336 if (insertion_block->number_of_preds() == 0) { | |
337 return; // only the entry block does not have a predecessor | |
338 } | |
339 | |
340 assert(insertion_block->end()->as_Base() == NULL, "cannot insert into entry block"); | |
341 _insertion_point = insertion_block->end()->prev(); | |
342 | |
343 BlockEnd *block_end = insertion_block->end(); | |
344 _state = block_end->state_before(); | |
345 | |
346 if (!_state) { | |
347 // If, TableSwitch and LookupSwitch always have state_before when | |
348 // loop invariant code motion happens.. | |
349 assert(block_end->as_Goto(), "Block has to be goto"); | |
350 _state = block_end->state(); | |
351 } | |
352 | |
353 // the loop_blocks are filled by going backward from the loop header, so this processing order is best | |
354 assert(loop_blocks->at(0) == loop_header, "loop header must be first loop block"); | |
355 process_block(loop_header); | |
356 for (int i = loop_blocks->length() - 1; i >= 1; i--) { | |
357 process_block(loop_blocks->at(i)); | |
358 } | |
359 } | |
360 | |
361 void LoopInvariantCodeMotion::process_block(BlockBegin* block) { | |
362 TRACE_VALUE_NUMBERING(tty->print_cr("processing block B%d", block->block_id())); | |
363 | |
364 Instruction* prev = block; | |
365 Instruction* cur = block->next(); | |
366 | |
367 while (cur != NULL) { | |
368 | |
369 // determine if cur instruction is loop invariant | |
370 // only selected instruction types are processed here | |
371 bool cur_invariant = false; | |
372 | |
373 if (cur->as_Constant() != NULL) { | |
374 cur_invariant = !cur->can_trap(); | |
375 } else if (cur->as_ArithmeticOp() != NULL || cur->as_LogicOp() != NULL || cur->as_ShiftOp() != NULL) { | |
376 assert(cur->as_Op2() != NULL, "must be Op2"); | |
377 Op2* op2 = (Op2*)cur; | |
378 cur_invariant = !op2->can_trap() && is_invariant(op2->x()) && is_invariant(op2->y()); | |
379 } else if (cur->as_LoadField() != NULL) { | |
380 LoadField* lf = (LoadField*)cur; | |
381 // deoptimizes on NullPointerException | |
382 cur_invariant = !lf->needs_patching() && !lf->field()->is_volatile() && !_short_loop_optimizer->has_field_store(lf->field()->type()->basic_type()) && is_invariant(lf->obj()); | |
383 } else if (cur->as_ArrayLength() != NULL) { | |
384 ArrayLength *length = cur->as_ArrayLength(); | |
385 cur_invariant = is_invariant(length->array()); | |
386 } else if (cur->as_LoadIndexed() != NULL) { | |
387 LoadIndexed *li = (LoadIndexed *)cur->as_LoadIndexed(); | |
388 cur_invariant = !_short_loop_optimizer->has_indexed_store(as_BasicType(cur->type())) && is_invariant(li->array()) && is_invariant(li->index()); | |
389 } | |
390 | |
391 if (cur_invariant) { | |
392 // perform value numbering and mark instruction as loop-invariant | |
393 _gvn->substitute(cur); | |
394 | |
395 if (cur->as_Constant() == NULL) { | |
396 // ensure that code for non-constant instructions is always generated | |
397 cur->pin(); | |
398 } | |
399 | |
400 // remove cur instruction from loop block and append it to block before loop | |
401 Instruction* next = cur->next(); | |
402 Instruction* in = _insertion_point->next(); | |
403 _insertion_point = _insertion_point->set_next(cur); | |
404 cur->set_next(in); | |
405 | |
406 // Deoptimize on exception | |
407 cur->set_flag(Instruction::DeoptimizeOnException, true); | |
408 | |
409 // Clear exception handlers | |
410 cur->set_exception_handlers(NULL); | |
411 | |
412 TRACE_VALUE_NUMBERING(tty->print_cr("Instruction %c%d is loop invariant", cur->type()->tchar(), cur->id())); | |
413 | |
414 if (cur->state_before() != NULL) { | |
415 cur->set_state_before(_state->copy()); | |
416 } | |
417 if (cur->exception_state() != NULL) { | |
418 cur->set_exception_state(_state->copy()); | |
419 } | |
420 | |
421 cur = prev->set_next(next); | |
422 | |
423 } else { | |
424 prev = cur; | |
425 cur = cur->next(); | |
426 } | |
427 } | |
428 } | |
298 | 429 |
299 bool ShortLoopOptimizer::process(BlockBegin* loop_header) { | 430 bool ShortLoopOptimizer::process(BlockBegin* loop_header) { |
300 TRACE_VALUE_NUMBERING(tty->print_cr("** loop header block")); | 431 TRACE_VALUE_NUMBERING(tty->print_cr("** loop header block")); |
301 | 432 |
302 _too_complicated_loop = false; | 433 _too_complicated_loop = false; |
313 } | 444 } |
314 | 445 |
315 // add predecessors to worklist | 446 // add predecessors to worklist |
316 for (int j = block->number_of_preds() - 1; j >= 0; j--) { | 447 for (int j = block->number_of_preds() - 1; j >= 0; j--) { |
317 BlockBegin* pred = block->pred_at(j); | 448 BlockBegin* pred = block->pred_at(j); |
449 | |
450 if (pred->is_set(BlockBegin::osr_entry_flag)) { | |
451 return false; | |
452 } | |
318 | 453 |
319 ValueMap* pred_map = value_map_of(pred); | 454 ValueMap* pred_map = value_map_of(pred); |
320 if (pred_map != NULL) { | 455 if (pred_map != NULL) { |
321 current_map()->kill_map(pred_map); | 456 current_map()->kill_map(pred_map); |
322 } else if (!_loop_blocks.contains(pred)) { | 457 } else if (!_loop_blocks.contains(pred)) { |
334 return false; | 469 return false; |
335 } | 470 } |
336 } | 471 } |
337 } | 472 } |
338 | 473 |
474 bool optimistic = this->_gvn->compilation()->is_optimistic(); | |
475 | |
476 if (UseLoopInvariantCodeMotion && optimistic) { | |
477 LoopInvariantCodeMotion code_motion(this, _gvn, loop_header, &_loop_blocks); | |
478 } | |
479 | |
339 TRACE_VALUE_NUMBERING(tty->print_cr("** loop successfully optimized")); | 480 TRACE_VALUE_NUMBERING(tty->print_cr("** loop successfully optimized")); |
340 return true; | 481 return true; |
341 } | 482 } |
342 | 483 |
343 | 484 |
344 GlobalValueNumbering::GlobalValueNumbering(IR* ir) | 485 GlobalValueNumbering::GlobalValueNumbering(IR* ir) |
345 : _current_map(NULL) | 486 : _current_map(NULL) |
346 , _value_maps(ir->linear_scan_order()->length(), NULL) | 487 , _value_maps(ir->linear_scan_order()->length(), NULL) |
488 , _compilation(ir->compilation()) | |
347 { | 489 { |
348 TRACE_VALUE_NUMBERING(tty->print_cr("****** start of global value numbering")); | 490 TRACE_VALUE_NUMBERING(tty->print_cr("****** start of global value numbering")); |
349 | 491 |
350 ShortLoopOptimizer short_loop_optimizer(this); | 492 ShortLoopOptimizer short_loop_optimizer(this); |
351 int subst_count = 0; | |
352 | 493 |
353 BlockList* blocks = ir->linear_scan_order(); | 494 BlockList* blocks = ir->linear_scan_order(); |
354 int num_blocks = blocks->length(); | 495 int num_blocks = blocks->length(); |
355 | 496 |
356 BlockBegin* start_block = blocks->at(0); | 497 BlockBegin* start_block = blocks->at(0); |
357 assert(start_block == ir->start() && start_block->number_of_preds() == 0 && start_block->dominator() == NULL, "must be start block"); | 498 assert(start_block == ir->start() && start_block->number_of_preds() == 0 && start_block->dominator() == NULL, "must be start block"); |
358 assert(start_block->next()->as_Base() != NULL && start_block->next()->next() == NULL, "start block must not have instructions"); | 499 assert(start_block->next()->as_Base() != NULL && start_block->next()->next() == NULL, "start block must not have instructions"); |
359 | 500 |
501 // method parameters are not linked in instructions list, so process them separateley | |
502 for_each_state_value(start_block->state(), value, | |
503 assert(value->as_Local() != NULL, "only method parameters allowed"); | |
504 set_processed(value); | |
505 ); | |
506 | |
360 // initial, empty value map with nesting 0 | 507 // initial, empty value map with nesting 0 |
361 set_value_map_of(start_block, new ValueMap()); | 508 set_value_map_of(start_block, new ValueMap()); |
362 | 509 |
363 for (int i = 1; i < num_blocks; i++) { | 510 for (int i = 1; i < num_blocks; i++) { |
364 BlockBegin* block = blocks->at(i); | 511 BlockBegin* block = blocks->at(i); |
372 assert(value_map_of(dominator) != NULL, "value map of dominator must exist"); | 519 assert(value_map_of(dominator) != NULL, "value map of dominator must exist"); |
373 | 520 |
374 // create new value map with increased nesting | 521 // create new value map with increased nesting |
375 _current_map = new ValueMap(value_map_of(dominator)); | 522 _current_map = new ValueMap(value_map_of(dominator)); |
376 | 523 |
377 if (num_preds == 1) { | 524 if (num_preds == 1 && !block->is_set(BlockBegin::exception_entry_flag)) { |
378 assert(dominator == block->pred_at(0), "dominator must be equal to predecessor"); | 525 assert(dominator == block->pred_at(0), "dominator must be equal to predecessor"); |
379 // nothing to do here | 526 // nothing to do here |
380 | 527 |
381 } else if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) { | 528 } else if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) { |
382 // block has incoming backward branches -> try to optimize short loops | 529 // block has incoming backward branches -> try to optimize short loops |
401 current_map()->kill_memory(); | 548 current_map()->kill_memory(); |
402 } | 549 } |
403 } | 550 } |
404 } | 551 } |
405 | 552 |
406 if (block->is_set(BlockBegin::exception_entry_flag)) { | 553 // phi functions are not linked in instructions list, so process them separateley |
407 current_map()->kill_exception(); | 554 for_each_phi_fun(block, phi, |
408 } | 555 set_processed(phi); |
556 ); | |
409 | 557 |
410 TRACE_VALUE_NUMBERING(tty->print("value map before processing block: "); current_map()->print()); | 558 TRACE_VALUE_NUMBERING(tty->print("value map before processing block: "); current_map()->print()); |
411 | 559 |
412 // visit all instructions of this block | 560 // visit all instructions of this block |
413 for (Value instr = block->next(); instr != NULL; instr = instr->next()) { | 561 for (Value instr = block->next(); instr != NULL; instr = instr->next()) { |
414 assert(!instr->has_subst(), "substitution already set"); | |
415 | |
416 // check if instruction kills any values | 562 // check if instruction kills any values |
417 instr->visit(this); | 563 instr->visit(this); |
418 | 564 // perform actual value numbering |
419 if (instr->hash() != 0) { | 565 substitute(instr); |
420 Value f = current_map()->find_insert(instr); | |
421 if (f != instr) { | |
422 assert(!f->has_subst(), "can't have a substitution"); | |
423 instr->set_subst(f); | |
424 subst_count++; | |
425 } | |
426 } | |
427 } | 566 } |
428 | 567 |
429 // remember value map for successors | 568 // remember value map for successors |
430 set_value_map_of(block, current_map()); | 569 set_value_map_of(block, current_map()); |
431 } | 570 } |
432 | 571 |
433 if (subst_count != 0) { | 572 if (_has_substitutions) { |
434 SubstitutionResolver resolver(ir); | 573 SubstitutionResolver resolver(ir); |
435 } | 574 } |
436 | 575 |
437 TRACE_VALUE_NUMBERING(tty->print("****** end of global value numbering. "); ValueMap::print_statistics()); | 576 TRACE_VALUE_NUMBERING(tty->print("****** end of global value numbering. "); ValueMap::print_statistics()); |
438 } | 577 } |
578 | |
579 void GlobalValueNumbering::substitute(Instruction* instr) { | |
580 assert(!instr->has_subst(), "substitution already set"); | |
581 Value subst = current_map()->find_insert(instr); | |
582 if (subst != instr) { | |
583 assert(!subst->has_subst(), "can't have a substitution"); | |
584 | |
585 TRACE_VALUE_NUMBERING(tty->print_cr("substitution for %d set to %d", instr->id(), subst->id())); | |
586 instr->set_subst(subst); | |
587 _has_substitutions = true; | |
588 } | |
589 set_processed(instr); | |
590 } |