Mercurial > hg > graal-jvmci-8
comparison src/share/vm/opto/ifg.cpp @ 14388:c84312468f5c
8031498: Cleanup and re-factorize PhaseChaitin::build_ifg_physical
Summary: Created sub-functions, added data structures, improved naming and removed unnecessary code
Reviewed-by: kvn, roland, rbackman
author | adlertz |
---|---|
date | Fri, 24 Jan 2014 13:06:52 +0100 |
parents | de6a9e811145 |
children | 99fc8c086679 |
comparison
equal
deleted
inserted
replaced
14387:303f79ab8e3d | 14388:c84312468f5c |
---|---|
279 assert(!lrgs(i)._degree_valid || effective_degree(i) == lrgs(i).degree(), "degree is valid but wrong"); | 279 assert(!lrgs(i)._degree_valid || effective_degree(i) == lrgs(i).degree(), "degree is valid but wrong"); |
280 } | 280 } |
281 } | 281 } |
282 #endif | 282 #endif |
283 | 283 |
284 // Interfere this register with everything currently live. Use the RegMasks | 284 /* |
285 // to trim the set of possible interferences. Return a count of register-only | 285 * Interfere this register with everything currently live. |
286 // interferences as an estimate of register pressure. | 286 * Check for interference by checking overlap of regmasks. |
287 void PhaseChaitin::interfere_with_live( uint r, IndexSet *liveout ) { | 287 * Only interfere if acceptable register masks overlap. |
288 uint retval = 0; | 288 */ |
289 // Interfere with everything live. | 289 void PhaseChaitin::interfere_with_live(uint lid, IndexSet* liveout) { |
290 const RegMask &rm = lrgs(r).mask(); | 290 LRG& lrg = lrgs(lid); |
291 // Check for interference by checking overlap of regmasks. | 291 const RegMask& rm = lrg.mask(); |
292 // Only interfere if acceptable register masks overlap. | |
293 IndexSetIterator elements(liveout); | 292 IndexSetIterator elements(liveout); |
294 uint l; | 293 uint interfering_lid = elements.next(); |
295 while( (l = elements.next()) != 0 ) | 294 while (interfering_lid != 0) { |
296 if( rm.overlap( lrgs(l).mask() ) ) | 295 LRG& interfering_lrg = lrgs(interfering_lid); |
297 _ifg->add_edge( r, l ); | 296 if (rm.overlap(interfering_lrg.mask())) { |
297 _ifg->add_edge(lid, interfering_lid); | |
298 } | |
299 interfering_lid = elements.next(); | |
300 } | |
298 } | 301 } |
299 | 302 |
300 // Actually build the interference graph. Uses virtual registers only, no | 303 // Actually build the interference graph. Uses virtual registers only, no |
301 // physical register masks. This allows me to be very aggressive when | 304 // physical register masks. This allows me to be very aggressive when |
302 // coalescing copies. Some of this aggressiveness will have to be undone | 305 // coalescing copies. Some of this aggressiveness will have to be undone |
331 liveout->remove(r); | 334 liveout->remove(r); |
332 | 335 |
333 // Copies do not define a new value and so do not interfere. | 336 // Copies do not define a new value and so do not interfere. |
334 // Remove the copies source from the liveout set before interfering. | 337 // Remove the copies source from the liveout set before interfering. |
335 uint idx = n->is_Copy(); | 338 uint idx = n->is_Copy(); |
336 if (idx) { | 339 if (idx != 0) { |
337 liveout->remove(_lrg_map.live_range_id(n->in(idx))); | 340 liveout->remove(_lrg_map.live_range_id(n->in(idx))); |
338 } | 341 } |
339 | 342 |
340 // Interfere with everything live | 343 // Interfere with everything live |
341 interfere_with_live(r, liveout); | 344 interfere_with_live(r, liveout); |
387 } | 390 } |
388 } // End of forall instructions in block | 391 } // End of forall instructions in block |
389 } // End of forall blocks | 392 } // End of forall blocks |
390 } | 393 } |
391 | 394 |
392 uint PhaseChaitin::count_int_pressure( IndexSet *liveout ) { | 395 #ifdef ASSERT |
396 uint PhaseChaitin::count_int_pressure(IndexSet* liveout) { | |
393 IndexSetIterator elements(liveout); | 397 IndexSetIterator elements(liveout); |
394 uint lidx; | 398 uint lidx = elements.next(); |
395 uint cnt = 0; | 399 uint cnt = 0; |
396 while ((lidx = elements.next()) != 0) { | 400 while (lidx != 0) { |
397 if( lrgs(lidx).mask().is_UP() && | 401 LRG& lrg = lrgs(lidx); |
398 lrgs(lidx).mask_size() && | 402 if (lrg.mask_is_nonempty_and_up() && |
399 !lrgs(lidx)._is_float && | 403 !lrg.is_float_or_vector() && |
400 !lrgs(lidx)._is_vector && | 404 lrg.mask().overlap(*Matcher::idealreg2regmask[Op_RegI])) { |
401 lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) | 405 cnt += lrg.reg_pressure(); |
402 cnt += lrgs(lidx).reg_pressure(); | 406 } |
407 lidx = elements.next(); | |
403 } | 408 } |
404 return cnt; | 409 return cnt; |
405 } | 410 } |
406 | 411 |
407 uint PhaseChaitin::count_float_pressure( IndexSet *liveout ) { | 412 uint PhaseChaitin::count_float_pressure(IndexSet* liveout) { |
408 IndexSetIterator elements(liveout); | 413 IndexSetIterator elements(liveout); |
409 uint lidx; | 414 uint lidx = elements.next(); |
410 uint cnt = 0; | 415 uint cnt = 0; |
411 while ((lidx = elements.next()) != 0) { | 416 while (lidx != 0) { |
412 if( lrgs(lidx).mask().is_UP() && | 417 LRG& lrg = lrgs(lidx); |
413 lrgs(lidx).mask_size() && | 418 if (lrg.mask_is_nonempty_and_up() && lrg.is_float_or_vector()) { |
414 (lrgs(lidx)._is_float || lrgs(lidx)._is_vector)) | 419 cnt += lrg.reg_pressure(); |
415 cnt += lrgs(lidx).reg_pressure(); | 420 } |
421 lidx = elements.next(); | |
416 } | 422 } |
417 return cnt; | 423 return cnt; |
418 } | 424 } |
419 | 425 #endif |
420 // Adjust register pressure down by 1. Capture last hi-to-low transition, | 426 |
421 static void lower_pressure( LRG *lrg, uint where, Block *b, uint *pressure, uint *hrp_index ) { | 427 /* |
422 if (lrg->mask().is_UP() && lrg->mask_size()) { | 428 * Adjust register pressure down by 1. Capture last hi-to-low transition, |
423 if (lrg->_is_float || lrg->_is_vector) { | 429 */ |
424 pressure[1] -= lrg->reg_pressure(); | 430 void PhaseChaitin::lower_pressure(Block* b, uint location, LRG& lrg, IndexSet* liveout, Pressure& int_pressure, Pressure& float_pressure) { |
425 if( pressure[1] == (uint)FLOATPRESSURE ) { | 431 if (lrg.mask_is_nonempty_and_up()) { |
426 hrp_index[1] = where; | 432 if (lrg.is_float_or_vector()) { |
427 if( pressure[1] > b->_freg_pressure ) | 433 float_pressure.lower(lrg, location); |
428 b->_freg_pressure = pressure[1]+1; | 434 } else { |
429 } | 435 // Do not count the SP and flag registers |
430 } else if( lrg->mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) { | 436 const RegMask& r = lrg.mask(); |
431 pressure[0] -= lrg->reg_pressure(); | 437 if (r.overlap(*Matcher::idealreg2regmask[Op_RegI])) { |
432 if( pressure[0] == (uint)INTPRESSURE ) { | 438 int_pressure.lower(lrg, location); |
433 hrp_index[0] = where; | 439 } |
434 if( pressure[0] > b->_reg_pressure ) | 440 } |
435 b->_reg_pressure = pressure[0]+1; | 441 } |
436 } | 442 assert(int_pressure._current_pressure == count_int_pressure(liveout), "the int pressure is incorrect"); |
437 } | 443 assert(float_pressure._current_pressure == count_float_pressure(liveout), "the float pressure is incorrect"); |
438 } | 444 } |
439 } | 445 |
440 | 446 /* Go to the first non-phi index in a block */ |
441 // Build the interference graph using physical registers when available. | 447 static uint first_nonphi_index(Block* b) { |
442 // That is, if 2 live ranges are simultaneously alive but in their acceptable | 448 uint i; |
443 // register sets do not overlap, then they do not interfere. | 449 uint end_idx = b->end_idx(); |
450 for (i = 1; i < end_idx; i++) { | |
451 Node* n = b->get_node(i); | |
452 if (!n->is_Phi()) { | |
453 break; | |
454 } | |
455 } | |
456 return i; | |
457 } | |
458 | |
459 /* | |
460 * Spills could be inserted before a CreateEx node which should be the first | |
461 * instruction in a block after Phi nodes. If so, move the CreateEx node up. | |
462 */ | |
463 static void move_exception_node_up(Block* b, uint first_inst, uint last_inst) { | |
464 for (uint i = first_inst; i < last_inst; i++) { | |
465 Node* ex = b->get_node(i); | |
466 if (ex->is_SpillCopy()) { | |
467 continue; | |
468 } | |
469 | |
470 if (i > first_inst && | |
471 ex->is_Mach() && ex->as_Mach()->ideal_Opcode() == Op_CreateEx) { | |
472 b->remove_node(i); | |
473 b->insert_node(ex, first_inst); | |
474 } | |
475 // Stop once a CreateEx or any other node is found | |
476 break; | |
477 } | |
478 } | |
479 | |
480 /* | |
481 * When new live ranges are live, we raise the register pressure | |
482 */ | |
483 void PhaseChaitin::raise_pressure(Block* b, LRG& lrg, Pressure& int_pressure, Pressure& float_pressure) { | |
484 if (lrg.mask_is_nonempty_and_up()) { | |
485 if (lrg.is_float_or_vector()) { | |
486 float_pressure.raise(lrg); | |
487 } else { | |
488 // Do not count the SP and flag registers | |
489 const RegMask& rm = lrg.mask(); | |
490 if (rm.overlap(*Matcher::idealreg2regmask[Op_RegI])) { | |
491 int_pressure.raise(lrg); | |
492 } | |
493 } | |
494 } | |
495 } | |
496 | |
497 | |
498 /* | |
499 * Computes the initial register pressure of a block, looking at all live | |
500 * ranges in the liveout. The register pressure is computed for both float | |
501 * and int/pointer registers. | |
502 * Live ranges in the liveout are presumed live for the whole block. | |
503 * We add the cost for the whole block to the area of the live ranges initially. | |
504 * If a live range gets killed in the block, we'll subtract the unused part of | |
505 * the block from the area. | |
506 */ | |
507 void PhaseChaitin::compute_initial_block_pressure(Block* b, IndexSet* liveout, Pressure& int_pressure, Pressure& float_pressure, double cost) { | |
508 IndexSetIterator elements(liveout); | |
509 uint lid = elements.next(); | |
510 while (lid != 0) { | |
511 LRG& lrg = lrgs(lid); | |
512 lrg._area += cost; | |
513 raise_pressure(b, lrg, int_pressure, float_pressure); | |
514 lid = elements.next(); | |
515 } | |
516 assert(int_pressure._current_pressure == count_int_pressure(liveout), "the int pressure is incorrect"); | |
517 assert(float_pressure._current_pressure == count_float_pressure(liveout), "the float pressure is incorrect"); | |
518 } | |
519 | |
520 /* | |
521 * Remove dead node if it's not used. | |
522 * We only remove projection nodes if the node "defining" the projection is | |
523 * dead, for example on x86, if we have a dead Add node we remove its | |
524 * RFLAGS node. | |
525 */ | |
526 bool PhaseChaitin::remove_node_if_not_used(Block* b, uint location, Node* n, uint lid, IndexSet* liveout) { | |
527 Node* def = n->in(0); | |
528 if (!n->is_Proj() || | |
529 (_lrg_map.live_range_id(def) && !liveout->member(_lrg_map.live_range_id(def)))) { | |
530 b->remove_node(location); | |
531 LRG& lrg = lrgs(lid); | |
532 if (lrg._def == n) { | |
533 lrg._def = 0; | |
534 } | |
535 n->disconnect_inputs(NULL, C); | |
536 _cfg.unmap_node_from_block(n); | |
537 n->replace_by(C->top()); | |
538 return true; | |
539 } | |
540 return false; | |
541 } | |
542 | |
543 /* | |
544 * When encountering a fat projection, we might go from a low to high to low | |
545 * (since the fat proj only lives at this instruction) going backwards in the | |
546 * block. If we find a low to high transition, we record it. | |
547 */ | |
548 void PhaseChaitin::check_for_high_pressure_transition_at_fatproj(uint& block_reg_pressure, uint location, LRG& lrg, Pressure& pressure, const int op_regtype) { | |
549 RegMask mask_tmp = lrg.mask(); | |
550 mask_tmp.AND(*Matcher::idealreg2regmask[op_regtype]); | |
551 // this pressure is only valid at this instruction, i.e. we don't need to lower | |
552 // the register pressure since the fat proj was never live before (going backwards) | |
553 uint new_pressure = pressure._current_pressure + mask_tmp.Size(); | |
554 if (new_pressure > pressure._final_pressure) { | |
555 pressure._final_pressure = new_pressure; | |
556 } | |
557 // if we were at a low pressure and now at the fat proj is at high pressure, record the fat proj location | |
558 // as coming from a low to high (to low again) | |
559 if (pressure._current_pressure <= pressure._high_pressure_limit && new_pressure > pressure._high_pressure_limit) { | |
560 pressure._high_pressure_index = location; | |
561 } | |
562 } | |
563 | |
564 /* | |
565 * Insure high score for immediate-use spill copies so they get a color. | |
566 * All single-use MachSpillCopy(s) that immediately precede their | |
567 * use must color early. If a longer live range steals their | |
568 * color, the spill copy will split and may push another spill copy | |
569 * further away resulting in an infinite spill-split-retry cycle. | |
570 * Assigning a zero area results in a high score() and a good | |
571 * location in the simplify list. | |
572 */ | |
573 void PhaseChaitin::assign_high_score_to_immediate_copies(Block* b, Node* n, LRG& lrg, uint next_inst, uint last_inst) { | |
574 if (n->is_SpillCopy() && | |
575 lrg.is_singledef() && // A multi defined live range can still split | |
576 n->outcnt() == 1 && // and use must be in this block | |
577 _cfg.get_block_for_node(n->unique_out()) == b) { | |
578 | |
579 Node* single_use = n->unique_out(); | |
580 assert(b->find_node(single_use) >= next_inst, "Use must be later in block"); | |
581 // Use can be earlier in block if it is a Phi, but then I should be a MultiDef | |
582 | |
583 // Find first non SpillCopy 'm' that follows the current instruction | |
584 // (current_inst - 1) is index for current instruction 'n' | |
585 Node* m = n; | |
586 for (uint i = next_inst; i <= last_inst && m->is_SpillCopy(); ++i) { | |
587 m = b->get_node(i); | |
588 } | |
589 if (m == single_use) { | |
590 lrg._area = 0.0; | |
591 } | |
592 } | |
593 } | |
594 | |
595 /* | |
596 * Copies do not define a new value and so do not interfere. | |
597 * Remove the copies source from the liveout set before interfering. | |
598 */ | |
599 void PhaseChaitin::remove_interference_from_copy(Block* b, uint location, uint lid_copy, IndexSet* liveout, double cost, Pressure& int_pressure, Pressure& float_pressure) { | |
600 if (liveout->remove(lid_copy)) { | |
601 LRG& lrg_copy = lrgs(lid_copy); | |
602 lrg_copy._area -= cost; | |
603 | |
604 // Lower register pressure since copy and definition can share the same register | |
605 lower_pressure(b, location, lrg_copy, liveout, int_pressure, float_pressure); | |
606 } | |
607 } | |
608 | |
609 /* | |
610 * The defined value must go in a particular register. Remove that register from | |
611 * all conflicting parties and avoid the interference. | |
612 */ | |
613 void PhaseChaitin::remove_bound_register_from_interfering_live_ranges(LRG& lrg, IndexSet* liveout, uint& must_spill) { | |
614 // Check for common case | |
615 const RegMask& rm = lrg.mask(); | |
616 int r_size = lrg.num_regs(); | |
617 // Smear odd bits | |
618 IndexSetIterator elements(liveout); | |
619 uint l = elements.next(); | |
620 while (l != 0) { | |
621 LRG& interfering_lrg = lrgs(l); | |
622 // If 'l' must spill already, do not further hack his bits. | |
623 // He'll get some interferences and be forced to spill later. | |
624 if (interfering_lrg._must_spill) { | |
625 l = elements.next(); | |
626 continue; | |
627 } | |
628 | |
629 // Remove bound register(s) from 'l's choices | |
630 RegMask old = interfering_lrg.mask(); | |
631 uint old_size = interfering_lrg.mask_size(); | |
632 | |
633 // Remove the bits from LRG 'rm' from LRG 'l' so 'l' no | |
634 // longer interferes with 'rm'. If 'l' requires aligned | |
635 // adjacent pairs, subtract out bit pairs. | |
636 assert(!interfering_lrg._is_vector || !interfering_lrg._fat_proj, "sanity"); | |
637 | |
638 if (interfering_lrg.num_regs() > 1 && !interfering_lrg._fat_proj) { | |
639 RegMask r2mask = rm; | |
640 // Leave only aligned set of bits. | |
641 r2mask.smear_to_sets(interfering_lrg.num_regs()); | |
642 // It includes vector case. | |
643 interfering_lrg.SUBTRACT(r2mask); | |
644 interfering_lrg.compute_set_mask_size(); | |
645 } else if (r_size != 1) { | |
646 // fat proj | |
647 interfering_lrg.SUBTRACT(rm); | |
648 interfering_lrg.compute_set_mask_size(); | |
649 } else { | |
650 // Common case: size 1 bound removal | |
651 OptoReg::Name r_reg = rm.find_first_elem(); | |
652 if (interfering_lrg.mask().Member(r_reg)) { | |
653 interfering_lrg.Remove(r_reg); | |
654 interfering_lrg.set_mask_size(interfering_lrg.mask().is_AllStack() ? LRG::AllStack_size : old_size - 1); | |
655 } | |
656 } | |
657 | |
658 // If 'l' goes completely dry, it must spill. | |
659 if (interfering_lrg.not_free()) { | |
660 // Give 'l' some kind of reasonable mask, so it picks up | |
661 // interferences (and will spill later). | |
662 interfering_lrg.set_mask(old); | |
663 interfering_lrg.set_mask_size(old_size); | |
664 must_spill++; | |
665 interfering_lrg._must_spill = 1; | |
666 interfering_lrg.set_reg(OptoReg::Name(LRG::SPILL_REG)); | |
667 } | |
668 l = elements.next(); | |
669 } | |
670 } | |
671 | |
672 /* | |
673 * Start loop at 1 (skip control edge) for most Nodes. SCMemProj's might be the | |
674 * sole use of a StoreLConditional. While StoreLConditionals set memory (the | |
675 * SCMemProj use) they also def flags; if that flag def is unused the allocator | |
676 * sees a flag-setting instruction with no use of the flags and assumes it's | |
677 * dead. This keeps the (useless) flag-setting behavior alive while also | |
678 * keeping the (useful) memory update effect. | |
679 */ | |
680 void PhaseChaitin::add_input_to_liveout(Block* b, Node* n, IndexSet* liveout, double cost, Pressure& int_pressure, Pressure& float_pressure) { | |
681 JVMState* jvms = n->jvms(); | |
682 uint debug_start = jvms ? jvms->debug_start() : 999999; | |
683 | |
684 for (uint k = ((n->Opcode() == Op_SCMemProj) ? 0:1); k < n->req(); k++) { | |
685 Node* def = n->in(k); | |
686 uint lid = _lrg_map.live_range_id(def); | |
687 if (!lid) { | |
688 continue; | |
689 } | |
690 LRG& lrg = lrgs(lid); | |
691 | |
692 // No use-side cost for spilling debug info | |
693 if (k < debug_start) { | |
694 // A USE costs twice block frequency (once for the Load, once | |
695 // for a Load-delay). Rematerialized uses only cost once. | |
696 lrg._cost += (def->rematerialize() ? b->_freq : (b->_freq * 2)); | |
697 } | |
698 | |
699 if (liveout->insert(lid)) { | |
700 // Newly live things assumed live from here to top of block | |
701 lrg._area += cost; | |
702 raise_pressure(b, lrg, int_pressure, float_pressure); | |
703 assert(int_pressure._current_pressure == count_int_pressure(liveout), "the int pressure is incorrect"); | |
704 assert(float_pressure._current_pressure == count_float_pressure(liveout), "the float pressure is incorrect"); | |
705 } | |
706 assert(!(lrg._area < 0.0), "negative spill area" ); | |
707 } | |
708 } | |
709 | |
710 /* | |
711 * If we run off the top of the block with high pressure just record that the | |
712 * whole block is high pressure. (Even though we might have a transition | |
713 * lower down in the block) | |
714 */ | |
715 void PhaseChaitin::check_for_high_pressure_block(Pressure& pressure) { | |
716 // current pressure now means the pressure before the first instruction in the block | |
717 // (since we have stepped through all instructions backwards) | |
718 if (pressure._current_pressure > pressure._high_pressure_limit) { | |
719 pressure._high_pressure_index = 0; | |
720 } | |
721 } | |
722 | |
723 /* | |
724 * Compute high pressure indice; avoid landing in the middle of projnodes | |
725 * and set the high pressure index for the block | |
726 */ | |
727 void PhaseChaitin::adjust_high_pressure_index(Block* b, uint& block_hrp_index, Pressure& pressure) { | |
728 uint i = pressure._high_pressure_index; | |
729 if (i < b->number_of_nodes() && i < b->end_idx() + 1) { | |
730 Node* cur = b->get_node(i); | |
731 while (cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch()) { | |
732 cur = b->get_node(--i); | |
733 } | |
734 } | |
735 block_hrp_index = i; | |
736 } | |
737 | |
738 /* Build an interference graph: | |
739 * That is, if 2 live ranges are simultaneously alive but in their acceptable | |
740 * register sets do not overlap, then they do not interfere. The IFG is built | |
741 * by a single reverse pass over each basic block. Starting with the known | |
742 * live-out set, we remove things that get defined and add things that become | |
743 * live (essentially executing one pass of a standard LIVE analysis). Just | |
744 * before a Node defines a value (and removes it from the live-ness set) that | |
745 * value is certainly live. The defined value interferes with everything | |
746 * currently live. The value is then removed from the live-ness set and it's | |
747 * inputs are added to the live-ness set. | |
748 * Compute register pressure for each block: | |
749 * We store the biggest register pressure for each block and also the first | |
750 * low to high register pressure transition within the block (if any). | |
751 */ | |
444 uint PhaseChaitin::build_ifg_physical( ResourceArea *a ) { | 752 uint PhaseChaitin::build_ifg_physical( ResourceArea *a ) { |
445 NOT_PRODUCT( Compile::TracePhase t3("buildIFG", &_t_buildIFGphysical, TimeCompiler); ) | 753 NOT_PRODUCT(Compile::TracePhase t3("buildIFG", &_t_buildIFGphysical, TimeCompiler);) |
446 | 754 |
447 uint must_spill = 0; | 755 uint must_spill = 0; |
448 | |
449 // For all blocks (in any order) do... | |
450 for (uint i = 0; i < _cfg.number_of_blocks(); i++) { | 756 for (uint i = 0; i < _cfg.number_of_blocks(); i++) { |
451 Block* block = _cfg.get_block(i); | 757 Block* block = _cfg.get_block(i); |
758 | |
452 // Clone (rather than smash in place) the liveout info, so it is alive | 759 // Clone (rather than smash in place) the liveout info, so it is alive |
453 // for the "collect_gc_info" phase later. | 760 // for the "collect_gc_info" phase later. |
454 IndexSet liveout(_live->live(block)); | 761 IndexSet liveout(_live->live(block)); |
762 | |
763 uint first_inst = first_nonphi_index(block); | |
455 uint last_inst = block->end_idx(); | 764 uint last_inst = block->end_idx(); |
456 // Compute first nonphi node index | 765 |
457 uint first_inst; | 766 move_exception_node_up(block, first_inst, last_inst); |
458 for (first_inst = 1; first_inst < last_inst; first_inst++) { | 767 |
459 if (!block->get_node(first_inst)->is_Phi()) { | 768 Pressure int_pressure(last_inst + 1, INTPRESSURE); |
460 break; | 769 Pressure float_pressure(last_inst + 1, FLOATPRESSURE); |
461 } | 770 block->_reg_pressure = 0; |
462 } | 771 block->_freg_pressure = 0; |
463 | 772 |
464 // Spills could be inserted before CreateEx node which should be | |
465 // first instruction in block after Phis. Move CreateEx up. | |
466 for (uint insidx = first_inst; insidx < last_inst; insidx++) { | |
467 Node *ex = block->get_node(insidx); | |
468 if (ex->is_SpillCopy()) { | |
469 continue; | |
470 } | |
471 if (insidx > first_inst && ex->is_Mach() && ex->as_Mach()->ideal_Opcode() == Op_CreateEx) { | |
472 // If the CreateEx isn't above all the MachSpillCopies | |
473 // then move it to the top. | |
474 block->remove_node(insidx); | |
475 block->insert_node(ex, first_inst); | |
476 } | |
477 // Stop once a CreateEx or any other node is found | |
478 break; | |
479 } | |
480 | |
481 // Reset block's register pressure values for each ifg construction | |
482 uint pressure[2], hrp_index[2]; | |
483 pressure[0] = pressure[1] = 0; | |
484 hrp_index[0] = hrp_index[1] = last_inst+1; | |
485 block->_reg_pressure = block->_freg_pressure = 0; | |
486 // Liveout things are presumed live for the whole block. We accumulate | |
487 // 'area' accordingly. If they get killed in the block, we'll subtract | |
488 // the unused part of the block from the area. | |
489 int inst_count = last_inst - first_inst; | 773 int inst_count = last_inst - first_inst; |
490 double cost = (inst_count <= 0) ? 0.0 : block->_freq * double(inst_count); | 774 double cost = (inst_count <= 0) ? 0.0 : block->_freq * double(inst_count); |
491 assert(!(cost < 0.0), "negative spill cost" ); | 775 assert(!(cost < 0.0), "negative spill cost" ); |
492 IndexSetIterator elements(&liveout); | 776 |
493 uint lidx; | 777 compute_initial_block_pressure(block, &liveout, int_pressure, float_pressure, cost); |
494 while ((lidx = elements.next()) != 0) { | 778 |
495 LRG &lrg = lrgs(lidx); | 779 for (uint location = last_inst; location > 0; location--) { |
496 lrg._area += cost; | 780 Node* n = block->get_node(location); |
497 // Compute initial register pressure | 781 uint lid = _lrg_map.live_range_id(n); |
498 if (lrg.mask().is_UP() && lrg.mask_size()) { | 782 |
499 if (lrg._is_float || lrg._is_vector) { // Count float pressure | 783 if(lid) { |
500 pressure[1] += lrg.reg_pressure(); | 784 LRG& lrg = lrgs(lid); |
501 if (pressure[1] > block->_freg_pressure) { | 785 |
502 block->_freg_pressure = pressure[1]; | 786 // A DEF normally costs block frequency; rematerialized values are |
787 // removed from the DEF sight, so LOWER costs here. | |
788 lrg._cost += n->rematerialize() ? 0 : block->_freq; | |
789 | |
790 if (!liveout.member(lid) && n->Opcode() != Op_SafePoint) { | |
791 if (remove_node_if_not_used(block, location, n, lid, &liveout)) { | |
792 float_pressure._high_pressure_index--; | |
793 int_pressure._high_pressure_index--; | |
794 continue; | |
503 } | 795 } |
504 // Count int pressure, but do not count the SP, flags | 796 if (lrg._fat_proj) { |
505 } else if(lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI])) { | 797 check_for_high_pressure_transition_at_fatproj(block->_reg_pressure, location, lrg, int_pressure, Op_RegI); |
506 pressure[0] += lrg.reg_pressure(); | 798 check_for_high_pressure_transition_at_fatproj(block->_freg_pressure, location, lrg, float_pressure, Op_RegD); |
507 if (pressure[0] > block->_reg_pressure) { | 799 } |
508 block->_reg_pressure = pressure[0]; | 800 } else { |
801 // A live range ends at its definition, remove the remaining area. | |
802 lrg._area -= cost; | |
803 assert(lrg._area >= 0.0, "negative spill area" ); | |
804 | |
805 assign_high_score_to_immediate_copies(block, n, lrg, location + 1, last_inst); | |
806 | |
807 if (liveout.remove(lid)) { | |
808 lower_pressure(block, location, lrg, &liveout, int_pressure, float_pressure); | |
809 } | |
810 uint copy_idx = n->is_Copy(); | |
811 if (copy_idx) { | |
812 uint lid_copy = _lrg_map.live_range_id(n->in(copy_idx)); | |
813 remove_interference_from_copy(block, location, lid_copy, &liveout, cost, int_pressure, float_pressure); | |
509 } | 814 } |
510 } | 815 } |
511 } | 816 |
512 } | 817 // Since rematerializable DEFs are not bound but the live range is, |
513 assert( pressure[0] == count_int_pressure (&liveout), "" ); | 818 // some uses must be bound. If we spill live range 'r', it can |
514 assert( pressure[1] == count_float_pressure(&liveout), "" ); | 819 // rematerialize at each use site according to its bindings. |
515 | 820 if (lrg.is_bound() && !n->rematerialize() && lrg.mask().is_NotEmpty()) { |
516 // The IFG is built by a single reverse pass over each basic block. | 821 remove_bound_register_from_interfering_live_ranges(lrg, &liveout, must_spill); |
517 // Starting with the known live-out set, we remove things that get | 822 } |
518 // defined and add things that become live (essentially executing one | 823 interfere_with_live(lid, &liveout); |
519 // pass of a standard LIVE analysis). Just before a Node defines a value | 824 } |
520 // (and removes it from the live-ness set) that value is certainly live. | |
521 // The defined value interferes with everything currently live. The | |
522 // value is then removed from the live-ness set and it's inputs are added | |
523 // to the live-ness set. | |
524 uint j; | |
525 for (j = last_inst + 1; j > 1; j--) { | |
526 Node* n = block->get_node(j - 1); | |
527 | |
528 // Get value being defined | |
529 uint r = _lrg_map.live_range_id(n); | |
530 | |
531 // Some special values do not allocate | |
532 if(r) { | |
533 // A DEF normally costs block frequency; rematerialized values are | |
534 // removed from the DEF sight, so LOWER costs here. | |
535 lrgs(r)._cost += n->rematerialize() ? 0 : block->_freq; | |
536 | |
537 // If it is not live, then this instruction is dead. Probably caused | |
538 // by spilling and rematerialization. Who cares why, yank this baby. | |
539 if( !liveout.member(r) && n->Opcode() != Op_SafePoint ) { | |
540 Node *def = n->in(0); | |
541 if( !n->is_Proj() || | |
542 // Could also be a flags-projection of a dead ADD or such. | |
543 (_lrg_map.live_range_id(def) && !liveout.member(_lrg_map.live_range_id(def)))) { | |
544 block->remove_node(j - 1); | |
545 if (lrgs(r)._def == n) { | |
546 lrgs(r)._def = 0; | |
547 } | |
548 n->disconnect_inputs(NULL, C); | |
549 _cfg.unmap_node_from_block(n); | |
550 n->replace_by(C->top()); | |
551 // Since yanking a Node from block, high pressure moves up one | |
552 hrp_index[0]--; | |
553 hrp_index[1]--; | |
554 continue; | |
555 } | |
556 | |
557 // Fat-projections kill many registers which cannot be used to | |
558 // hold live ranges. | |
559 if (lrgs(r)._fat_proj) { | |
560 // Count the int-only registers | |
561 RegMask itmp = lrgs(r).mask(); | |
562 itmp.AND(*Matcher::idealreg2regmask[Op_RegI]); | |
563 int iregs = itmp.Size(); | |
564 if (pressure[0]+iregs > block->_reg_pressure) { | |
565 block->_reg_pressure = pressure[0] + iregs; | |
566 } | |
567 if (pressure[0] <= (uint)INTPRESSURE && pressure[0] + iregs > (uint)INTPRESSURE) { | |
568 hrp_index[0] = j - 1; | |
569 } | |
570 // Count the float-only registers | |
571 RegMask ftmp = lrgs(r).mask(); | |
572 ftmp.AND(*Matcher::idealreg2regmask[Op_RegD]); | |
573 int fregs = ftmp.Size(); | |
574 if (pressure[1] + fregs > block->_freg_pressure) { | |
575 block->_freg_pressure = pressure[1] + fregs; | |
576 } | |
577 if(pressure[1] <= (uint)FLOATPRESSURE && pressure[1]+fregs > (uint)FLOATPRESSURE) { | |
578 hrp_index[1] = j - 1; | |
579 } | |
580 } | |
581 | |
582 } else { // Else it is live | |
583 // A DEF also ends 'area' partway through the block. | |
584 lrgs(r)._area -= cost; | |
585 assert(!(lrgs(r)._area < 0.0), "negative spill area" ); | |
586 | |
587 // Insure high score for immediate-use spill copies so they get a color | |
588 if( n->is_SpillCopy() | |
589 && lrgs(r).is_singledef() // MultiDef live range can still split | |
590 && n->outcnt() == 1 // and use must be in this block | |
591 && _cfg.get_block_for_node(n->unique_out()) == block) { | |
592 // All single-use MachSpillCopy(s) that immediately precede their | |
593 // use must color early. If a longer live range steals their | |
594 // color, the spill copy will split and may push another spill copy | |
595 // further away resulting in an infinite spill-split-retry cycle. | |
596 // Assigning a zero area results in a high score() and a good | |
597 // location in the simplify list. | |
598 // | |
599 | |
600 Node *single_use = n->unique_out(); | |
601 assert(block->find_node(single_use) >= j, "Use must be later in block"); | |
602 // Use can be earlier in block if it is a Phi, but then I should be a MultiDef | |
603 | |
604 // Find first non SpillCopy 'm' that follows the current instruction | |
605 // (j - 1) is index for current instruction 'n' | |
606 Node *m = n; | |
607 for (uint i = j; i <= last_inst && m->is_SpillCopy(); ++i) { | |
608 m = block->get_node(i); | |
609 } | |
610 if (m == single_use) { | |
611 lrgs(r)._area = 0.0; | |
612 } | |
613 } | |
614 | |
615 // Remove from live-out set | |
616 if( liveout.remove(r) ) { | |
617 // Adjust register pressure. | |
618 // Capture last hi-to-lo pressure transition | |
619 lower_pressure(&lrgs(r), j - 1, block, pressure, hrp_index); | |
620 assert( pressure[0] == count_int_pressure (&liveout), "" ); | |
621 assert( pressure[1] == count_float_pressure(&liveout), "" ); | |
622 } | |
623 | |
624 // Copies do not define a new value and so do not interfere. | |
625 // Remove the copies source from the liveout set before interfering. | |
626 uint idx = n->is_Copy(); | |
627 if (idx) { | |
628 uint x = _lrg_map.live_range_id(n->in(idx)); | |
629 if (liveout.remove(x)) { | |
630 lrgs(x)._area -= cost; | |
631 // Adjust register pressure. | |
632 lower_pressure(&lrgs(x), j - 1, block, pressure, hrp_index); | |
633 assert( pressure[0] == count_int_pressure (&liveout), "" ); | |
634 assert( pressure[1] == count_float_pressure(&liveout), "" ); | |
635 } | |
636 } | |
637 } // End of if live or not | |
638 | |
639 // Interfere with everything live. If the defined value must | |
640 // go in a particular register, just remove that register from | |
641 // all conflicting parties and avoid the interference. | |
642 | |
643 // Make exclusions for rematerializable defs. Since rematerializable | |
644 // DEFs are not bound but the live range is, some uses must be bound. | |
645 // If we spill live range 'r', it can rematerialize at each use site | |
646 // according to its bindings. | |
647 const RegMask &rmask = lrgs(r).mask(); | |
648 if( lrgs(r).is_bound() && !(n->rematerialize()) && rmask.is_NotEmpty() ) { | |
649 // Check for common case | |
650 int r_size = lrgs(r).num_regs(); | |
651 OptoReg::Name r_reg = (r_size == 1) ? rmask.find_first_elem() : OptoReg::Physical; | |
652 // Smear odd bits | |
653 IndexSetIterator elements(&liveout); | |
654 uint l; | |
655 while ((l = elements.next()) != 0) { | |
656 LRG &lrg = lrgs(l); | |
657 // If 'l' must spill already, do not further hack his bits. | |
658 // He'll get some interferences and be forced to spill later. | |
659 if( lrg._must_spill ) continue; | |
660 // Remove bound register(s) from 'l's choices | |
661 RegMask old = lrg.mask(); | |
662 uint old_size = lrg.mask_size(); | |
663 // Remove the bits from LRG 'r' from LRG 'l' so 'l' no | |
664 // longer interferes with 'r'. If 'l' requires aligned | |
665 // adjacent pairs, subtract out bit pairs. | |
666 assert(!lrg._is_vector || !lrg._fat_proj, "sanity"); | |
667 if (lrg.num_regs() > 1 && !lrg._fat_proj) { | |
668 RegMask r2mask = rmask; | |
669 // Leave only aligned set of bits. | |
670 r2mask.smear_to_sets(lrg.num_regs()); | |
671 // It includes vector case. | |
672 lrg.SUBTRACT( r2mask ); | |
673 lrg.compute_set_mask_size(); | |
674 } else if( r_size != 1 ) { // fat proj | |
675 lrg.SUBTRACT( rmask ); | |
676 lrg.compute_set_mask_size(); | |
677 } else { // Common case: size 1 bound removal | |
678 if( lrg.mask().Member(r_reg) ) { | |
679 lrg.Remove(r_reg); | |
680 lrg.set_mask_size(lrg.mask().is_AllStack() ? LRG::AllStack_size : old_size - 1); | |
681 } | |
682 } | |
683 // If 'l' goes completely dry, it must spill. | |
684 if( lrg.not_free() ) { | |
685 // Give 'l' some kind of reasonable mask, so he picks up | |
686 // interferences (and will spill later). | |
687 lrg.set_mask( old ); | |
688 lrg.set_mask_size(old_size); | |
689 must_spill++; | |
690 lrg._must_spill = 1; | |
691 lrg.set_reg(OptoReg::Name(LRG::SPILL_REG)); | |
692 } | |
693 } | |
694 } // End of if bound | |
695 | |
696 // Now interference with everything that is live and has | |
697 // compatible register sets. | |
698 interfere_with_live(r,&liveout); | |
699 | |
700 } // End of if normal register-allocated value | |
701 | 825 |
702 // Area remaining in the block | 826 // Area remaining in the block |
703 inst_count--; | 827 inst_count--; |
704 cost = (inst_count <= 0) ? 0.0 : block->_freq * double(inst_count); | 828 cost = (inst_count <= 0) ? 0.0 : block->_freq * double(inst_count); |
705 | 829 |
706 // Make all inputs live | 830 if (!n->is_Phi()) { |
707 if( !n->is_Phi() ) { // Phi function uses come from prior block | 831 add_input_to_liveout(block, n, &liveout, cost, int_pressure, float_pressure); |
708 JVMState* jvms = n->jvms(); | 832 } |
709 uint debug_start = jvms ? jvms->debug_start() : 999999; | 833 } |
710 // Start loop at 1 (skip control edge) for most Nodes. | 834 |
711 // SCMemProj's might be the sole use of a StoreLConditional. | 835 check_for_high_pressure_block(int_pressure); |
712 // While StoreLConditionals set memory (the SCMemProj use) | 836 check_for_high_pressure_block(float_pressure); |
713 // they also def flags; if that flag def is unused the | 837 adjust_high_pressure_index(block, block->_ihrp_index, int_pressure); |
714 // allocator sees a flag-setting instruction with no use of | 838 adjust_high_pressure_index(block, block->_fhrp_index, float_pressure); |
715 // the flags and assumes it's dead. This keeps the (useless) | 839 // set the final_pressure as the register pressure for the block |
716 // flag-setting behavior alive while also keeping the (useful) | 840 block->_reg_pressure = int_pressure._final_pressure; |
717 // memory update effect. | 841 block->_freg_pressure = float_pressure._final_pressure; |
718 for (uint k = ((n->Opcode() == Op_SCMemProj) ? 0:1); k < n->req(); k++) { | |
719 Node *def = n->in(k); | |
720 uint x = _lrg_map.live_range_id(def); | |
721 if (!x) { | |
722 continue; | |
723 } | |
724 LRG &lrg = lrgs(x); | |
725 // No use-side cost for spilling debug info | |
726 if (k < debug_start) { | |
727 // A USE costs twice block frequency (once for the Load, once | |
728 // for a Load-delay). Rematerialized uses only cost once. | |
729 lrg._cost += (def->rematerialize() ? block->_freq : (block->_freq + block->_freq)); | |
730 } | |
731 // It is live now | |
732 if (liveout.insert(x)) { | |
733 // Newly live things assumed live from here to top of block | |
734 lrg._area += cost; | |
735 // Adjust register pressure | |
736 if (lrg.mask().is_UP() && lrg.mask_size()) { | |
737 if (lrg._is_float || lrg._is_vector) { | |
738 pressure[1] += lrg.reg_pressure(); | |
739 if (pressure[1] > block->_freg_pressure) { | |
740 block->_freg_pressure = pressure[1]; | |
741 } | |
742 } else if( lrg.mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) { | |
743 pressure[0] += lrg.reg_pressure(); | |
744 if (pressure[0] > block->_reg_pressure) { | |
745 block->_reg_pressure = pressure[0]; | |
746 } | |
747 } | |
748 } | |
749 assert( pressure[0] == count_int_pressure (&liveout), "" ); | |
750 assert( pressure[1] == count_float_pressure(&liveout), "" ); | |
751 } | |
752 assert(!(lrg._area < 0.0), "negative spill area" ); | |
753 } | |
754 } | |
755 } // End of reverse pass over all instructions in block | |
756 | |
757 // If we run off the top of the block with high pressure and | |
758 // never see a hi-to-low pressure transition, just record that | |
759 // the whole block is high pressure. | |
760 if (pressure[0] > (uint)INTPRESSURE) { | |
761 hrp_index[0] = 0; | |
762 if (pressure[0] > block->_reg_pressure) { | |
763 block->_reg_pressure = pressure[0]; | |
764 } | |
765 } | |
766 if (pressure[1] > (uint)FLOATPRESSURE) { | |
767 hrp_index[1] = 0; | |
768 if (pressure[1] > block->_freg_pressure) { | |
769 block->_freg_pressure = pressure[1]; | |
770 } | |
771 } | |
772 | |
773 // Compute high pressure indice; avoid landing in the middle of projnodes | |
774 j = hrp_index[0]; | |
775 if (j < block->number_of_nodes() && j < block->end_idx() + 1) { | |
776 Node* cur = block->get_node(j); | |
777 while (cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch()) { | |
778 j--; | |
779 cur = block->get_node(j); | |
780 } | |
781 } | |
782 block->_ihrp_index = j; | |
783 j = hrp_index[1]; | |
784 if (j < block->number_of_nodes() && j < block->end_idx() + 1) { | |
785 Node* cur = block->get_node(j); | |
786 while (cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch()) { | |
787 j--; | |
788 cur = block->get_node(j); | |
789 } | |
790 } | |
791 block->_fhrp_index = j; | |
792 | 842 |
793 #ifndef PRODUCT | 843 #ifndef PRODUCT |
794 // Gather Register Pressure Statistics | 844 // Gather Register Pressure Statistics |
795 if( PrintOptoStatistics ) { | 845 if (PrintOptoStatistics) { |
796 if (block->_reg_pressure > (uint)INTPRESSURE || block->_freg_pressure > (uint)FLOATPRESSURE) { | 846 if (block->_reg_pressure > int_pressure._high_pressure_limit || block->_freg_pressure > float_pressure._high_pressure_limit) { |
797 _high_pressure++; | 847 _high_pressure++; |
798 } else { | 848 } else { |
799 _low_pressure++; | 849 _low_pressure++; |
800 } | 850 } |
801 } | 851 } |
802 #endif | 852 #endif |
803 } // End of for all blocks | 853 } |
804 | 854 |
805 return must_spill; | 855 return must_spill; |
806 } | 856 } |