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 "compiler/oopMap.hpp"
27 #include "memory/allocation.inline.hpp"
28 #include "opto/addnode.hpp"
29 #include "opto/block.hpp"
30 #include "opto/callnode.hpp"
31 #include "opto/cfgnode.hpp"
32 #include "opto/chaitin.hpp"
33 #include "opto/coalesce.hpp"
34 #include "opto/connode.hpp"
35 #include "opto/indexSet.hpp"
36 #include "opto/machnode.hpp"
37 #include "opto/memnode.hpp"
38 #include "opto/opcodes.hpp"
39
40 #define EXACT_PRESSURE 1
41
42 //=============================================================================
43 //------------------------------IFG--------------------------------------------
44 PhaseIFG::PhaseIFG( Arena *arena ) : Phase(Interference_Graph), _arena(arena) {
45 }
46
47 //------------------------------init-------------------------------------------
48 void PhaseIFG::init( uint maxlrg ) {
49 _maxlrg = maxlrg;
50 _yanked = new (_arena) VectorSet(_arena);
51 _is_square = false;
52 // Make uninitialized adjacency lists
53 _adjs = (IndexSet*)_arena->Amalloc(sizeof(IndexSet)*maxlrg);
54 // Also make empty live range structures
55 _lrgs = (LRG *)_arena->Amalloc( maxlrg * sizeof(LRG) );
56 memset(_lrgs,0,sizeof(LRG)*maxlrg);
57 // Init all to empty
58 for( uint i = 0; i < maxlrg; i++ ) {
59 _adjs[i].initialize(maxlrg);
60 _lrgs[i].Set_All();
61 }
428 IndexSetIterator elements(liveout);
429 uint lidx;
430 uint cnt = 0;
431 while ((lidx = elements.next()) != 0) {
432 if( lrgs(lidx).mask().is_UP() &&
433 lrgs(lidx).mask_size() &&
434 (lrgs(lidx)._is_float || lrgs(lidx)._is_vector))
435 cnt += lrgs(lidx).reg_pressure();
436 }
437 return cnt;
438 }
439
440 //------------------------------lower_pressure---------------------------------
441 // Adjust register pressure down by 1. Capture last hi-to-low transition,
442 static void lower_pressure( LRG *lrg, uint where, Block *b, uint *pressure, uint *hrp_index ) {
443 if (lrg->mask().is_UP() && lrg->mask_size()) {
444 if (lrg->_is_float || lrg->_is_vector) {
445 pressure[1] -= lrg->reg_pressure();
446 if( pressure[1] == (uint)FLOATPRESSURE ) {
447 hrp_index[1] = where;
448 #ifdef EXACT_PRESSURE
449 if( pressure[1] > b->_freg_pressure )
450 b->_freg_pressure = pressure[1]+1;
451 #else
452 b->_freg_pressure = (uint)FLOATPRESSURE+1;
453 #endif
454 }
455 } else if( lrg->mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {
456 pressure[0] -= lrg->reg_pressure();
457 if( pressure[0] == (uint)INTPRESSURE ) {
458 hrp_index[0] = where;
459 #ifdef EXACT_PRESSURE
460 if( pressure[0] > b->_reg_pressure )
461 b->_reg_pressure = pressure[0]+1;
462 #else
463 b->_reg_pressure = (uint)INTPRESSURE+1;
464 #endif
465 }
466 }
467 }
468 }
469
470 //------------------------------build_ifg_physical-----------------------------
471 // Build the interference graph using physical registers when available.
472 // That is, if 2 live ranges are simultaneously alive but in their acceptable
473 // register sets do not overlap, then they do not interfere.
474 uint PhaseChaitin::build_ifg_physical( ResourceArea *a ) {
475 NOT_PRODUCT( Compile::TracePhase t3("buildIFG", &_t_buildIFGphysical, TimeCompiler); )
476
477 uint spill_reg = LRG::SPILL_REG;
478 uint must_spill = 0;
479
480 // For all blocks (in any order) do...
481 for( uint i = 0; i < _cfg._num_blocks; i++ ) {
482 Block *b = _cfg._blocks[i];
483 // Clone (rather than smash in place) the liveout info, so it is alive
484 // for the "collect_gc_info" phase later.
509 // Reset block's register pressure values for each ifg construction
510 uint pressure[2], hrp_index[2];
511 pressure[0] = pressure[1] = 0;
512 hrp_index[0] = hrp_index[1] = last_inst+1;
513 b->_reg_pressure = b->_freg_pressure = 0;
514 // Liveout things are presumed live for the whole block. We accumulate
515 // 'area' accordingly. If they get killed in the block, we'll subtract
516 // the unused part of the block from the area.
517 int inst_count = last_inst - first_inst;
518 double cost = (inst_count <= 0) ? 0.0 : b->_freq * double(inst_count);
519 assert(!(cost < 0.0), "negative spill cost" );
520 IndexSetIterator elements(&liveout);
521 uint lidx;
522 while ((lidx = elements.next()) != 0) {
523 LRG &lrg = lrgs(lidx);
524 lrg._area += cost;
525 // Compute initial register pressure
526 if (lrg.mask().is_UP() && lrg.mask_size()) {
527 if (lrg._is_float || lrg._is_vector) { // Count float pressure
528 pressure[1] += lrg.reg_pressure();
529 #ifdef EXACT_PRESSURE
530 if( pressure[1] > b->_freg_pressure )
531 b->_freg_pressure = pressure[1];
532 #endif
533 // Count int pressure, but do not count the SP, flags
534 } else if( lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {
535 pressure[0] += lrg.reg_pressure();
536 #ifdef EXACT_PRESSURE
537 if( pressure[0] > b->_reg_pressure )
538 b->_reg_pressure = pressure[0];
539 #endif
540 }
541 }
542 }
543 assert( pressure[0] == count_int_pressure (&liveout), "" );
544 assert( pressure[1] == count_float_pressure(&liveout), "" );
545
546 // The IFG is built by a single reverse pass over each basic block.
547 // Starting with the known live-out set, we remove things that get
548 // defined and add things that become live (essentially executing one
549 // pass of a standard LIVE analysis). Just before a Node defines a value
550 // (and removes it from the live-ness set) that value is certainly live.
551 // The defined value interferes with everything currently live. The
552 // value is then removed from the live-ness set and it's inputs are added
553 // to the live-ness set.
554 uint j;
555 for( j = last_inst + 1; j > 1; j-- ) {
556 Node *n = b->_nodes[j - 1];
557
558 // Get value being defined
559 uint r = n2lidx(n);
572 // Could also be a flags-projection of a dead ADD or such.
573 (n2lidx(def) && !liveout.member(n2lidx(def)) ) ) {
574 b->_nodes.remove(j - 1);
575 if( lrgs(r)._def == n ) lrgs(r)._def = 0;
576 n->disconnect_inputs(NULL, C);
577 _cfg._bbs.map(n->_idx,NULL);
578 n->replace_by(C->top());
579 // Since yanking a Node from block, high pressure moves up one
580 hrp_index[0]--;
581 hrp_index[1]--;
582 continue;
583 }
584
585 // Fat-projections kill many registers which cannot be used to
586 // hold live ranges.
587 if( lrgs(r)._fat_proj ) {
588 // Count the int-only registers
589 RegMask itmp = lrgs(r).mask();
590 itmp.AND(*Matcher::idealreg2regmask[Op_RegI]);
591 int iregs = itmp.Size();
592 #ifdef EXACT_PRESSURE
593 if( pressure[0]+iregs > b->_reg_pressure )
594 b->_reg_pressure = pressure[0]+iregs;
595 #endif
596 if( pressure[0] <= (uint)INTPRESSURE &&
597 pressure[0]+iregs > (uint)INTPRESSURE ) {
598 #ifndef EXACT_PRESSURE
599 b->_reg_pressure = (uint)INTPRESSURE+1;
600 #endif
601 hrp_index[0] = j-1;
602 }
603 // Count the float-only registers
604 RegMask ftmp = lrgs(r).mask();
605 ftmp.AND(*Matcher::idealreg2regmask[Op_RegD]);
606 int fregs = ftmp.Size();
607 #ifdef EXACT_PRESSURE
608 if( pressure[1]+fregs > b->_freg_pressure )
609 b->_freg_pressure = pressure[1]+fregs;
610 #endif
611 if( pressure[1] <= (uint)FLOATPRESSURE &&
612 pressure[1]+fregs > (uint)FLOATPRESSURE ) {
613 #ifndef EXACT_PRESSURE
614 b->_freg_pressure = (uint)FLOATPRESSURE+1;
615 #endif
616 hrp_index[1] = j-1;
617 }
618 }
619
620 } else { // Else it is live
621 // A DEF also ends 'area' partway through the block.
622 lrgs(r)._area -= cost;
623 assert(!(lrgs(r)._area < 0.0), "negative spill area" );
624
625 // Insure high score for immediate-use spill copies so they get a color
626 if( n->is_SpillCopy()
627 && lrgs(r).is_singledef() // MultiDef live range can still split
628 && n->outcnt() == 1 // and use must be in this block
629 && _cfg._bbs[n->unique_out()->_idx] == b ) {
630 // All single-use MachSpillCopy(s) that immediately precede their
631 // use must color early. If a longer live range steals their
632 // color, the spill copy will split and may push another spill copy
633 // further away resulting in an infinite spill-split-retry cycle.
634 // Assigning a zero area results in a high score() and a good
635 // location in the simplify list.
752 // flag-setting behavior alive while also keeping the (useful)
753 // memory update effect.
754 for( uint k = ((n->Opcode() == Op_SCMemProj) ? 0:1); k < n->req(); k++ ) {
755 Node *def = n->in(k);
756 uint x = n2lidx(def);
757 if( !x ) continue;
758 LRG &lrg = lrgs(x);
759 // No use-side cost for spilling debug info
760 if( k < debug_start )
761 // A USE costs twice block frequency (once for the Load, once
762 // for a Load-delay). Rematerialized uses only cost once.
763 lrg._cost += (def->rematerialize() ? b->_freq : (b->_freq + b->_freq));
764 // It is live now
765 if( liveout.insert( x ) ) {
766 // Newly live things assumed live from here to top of block
767 lrg._area += cost;
768 // Adjust register pressure
769 if (lrg.mask().is_UP() && lrg.mask_size()) {
770 if (lrg._is_float || lrg._is_vector) {
771 pressure[1] += lrg.reg_pressure();
772 #ifdef EXACT_PRESSURE
773 if( pressure[1] > b->_freg_pressure )
774 b->_freg_pressure = pressure[1];
775 #endif
776 } else if( lrg.mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {
777 pressure[0] += lrg.reg_pressure();
778 #ifdef EXACT_PRESSURE
779 if( pressure[0] > b->_reg_pressure )
780 b->_reg_pressure = pressure[0];
781 #endif
782 }
783 }
784 assert( pressure[0] == count_int_pressure (&liveout), "" );
785 assert( pressure[1] == count_float_pressure(&liveout), "" );
786 }
787 assert(!(lrg._area < 0.0), "negative spill area" );
788 }
789 }
790 } // End of reverse pass over all instructions in block
791
792 // If we run off the top of the block with high pressure and
793 // never see a hi-to-low pressure transition, just record that
794 // the whole block is high pressure.
795 if( pressure[0] > (uint)INTPRESSURE ) {
796 hrp_index[0] = 0;
797 #ifdef EXACT_PRESSURE
798 if( pressure[0] > b->_reg_pressure )
799 b->_reg_pressure = pressure[0];
800 #else
801 b->_reg_pressure = (uint)INTPRESSURE+1;
802 #endif
803 }
804 if( pressure[1] > (uint)FLOATPRESSURE ) {
805 hrp_index[1] = 0;
806 #ifdef EXACT_PRESSURE
807 if( pressure[1] > b->_freg_pressure )
808 b->_freg_pressure = pressure[1];
809 #else
810 b->_freg_pressure = (uint)FLOATPRESSURE+1;
811 #endif
812 }
813
814 // Compute high pressure indice; avoid landing in the middle of projnodes
815 j = hrp_index[0];
816 if( j < b->_nodes.size() && j < b->end_idx()+1 ) {
817 Node *cur = b->_nodes[j];
818 while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) {
819 j--;
820 cur = b->_nodes[j];
821 }
822 }
823 b->_ihrp_index = j;
824 j = hrp_index[1];
825 if( j < b->_nodes.size() && j < b->end_idx()+1 ) {
826 Node *cur = b->_nodes[j];
827 while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) {
828 j--;
829 cur = b->_nodes[j];
830 }
831 }
|
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 "compiler/oopMap.hpp"
27 #include "memory/allocation.inline.hpp"
28 #include "opto/addnode.hpp"
29 #include "opto/block.hpp"
30 #include "opto/callnode.hpp"
31 #include "opto/cfgnode.hpp"
32 #include "opto/chaitin.hpp"
33 #include "opto/coalesce.hpp"
34 #include "opto/connode.hpp"
35 #include "opto/indexSet.hpp"
36 #include "opto/machnode.hpp"
37 #include "opto/memnode.hpp"
38 #include "opto/opcodes.hpp"
39
40 //=============================================================================
41 //------------------------------IFG--------------------------------------------
42 PhaseIFG::PhaseIFG( Arena *arena ) : Phase(Interference_Graph), _arena(arena) {
43 }
44
45 //------------------------------init-------------------------------------------
46 void PhaseIFG::init( uint maxlrg ) {
47 _maxlrg = maxlrg;
48 _yanked = new (_arena) VectorSet(_arena);
49 _is_square = false;
50 // Make uninitialized adjacency lists
51 _adjs = (IndexSet*)_arena->Amalloc(sizeof(IndexSet)*maxlrg);
52 // Also make empty live range structures
53 _lrgs = (LRG *)_arena->Amalloc( maxlrg * sizeof(LRG) );
54 memset(_lrgs,0,sizeof(LRG)*maxlrg);
55 // Init all to empty
56 for( uint i = 0; i < maxlrg; i++ ) {
57 _adjs[i].initialize(maxlrg);
58 _lrgs[i].Set_All();
59 }
426 IndexSetIterator elements(liveout);
427 uint lidx;
428 uint cnt = 0;
429 while ((lidx = elements.next()) != 0) {
430 if( lrgs(lidx).mask().is_UP() &&
431 lrgs(lidx).mask_size() &&
432 (lrgs(lidx)._is_float || lrgs(lidx)._is_vector))
433 cnt += lrgs(lidx).reg_pressure();
434 }
435 return cnt;
436 }
437
438 //------------------------------lower_pressure---------------------------------
439 // Adjust register pressure down by 1. Capture last hi-to-low transition,
440 static void lower_pressure( LRG *lrg, uint where, Block *b, uint *pressure, uint *hrp_index ) {
441 if (lrg->mask().is_UP() && lrg->mask_size()) {
442 if (lrg->_is_float || lrg->_is_vector) {
443 pressure[1] -= lrg->reg_pressure();
444 if( pressure[1] == (uint)FLOATPRESSURE ) {
445 hrp_index[1] = where;
446
447 if( pressure[1] > b->_freg_pressure )
448 b->_freg_pressure = pressure[1]+1;
449 }
450 } else if( lrg->mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {
451 pressure[0] -= lrg->reg_pressure();
452 if( pressure[0] == (uint)INTPRESSURE ) {
453 hrp_index[0] = where;
454
455 if( pressure[0] > b->_reg_pressure )
456 b->_reg_pressure = pressure[0]+1;
457 }
458 }
459 }
460 }
461
462 //------------------------------build_ifg_physical-----------------------------
463 // Build the interference graph using physical registers when available.
464 // That is, if 2 live ranges are simultaneously alive but in their acceptable
465 // register sets do not overlap, then they do not interfere.
466 uint PhaseChaitin::build_ifg_physical( ResourceArea *a ) {
467 NOT_PRODUCT( Compile::TracePhase t3("buildIFG", &_t_buildIFGphysical, TimeCompiler); )
468
469 uint spill_reg = LRG::SPILL_REG;
470 uint must_spill = 0;
471
472 // For all blocks (in any order) do...
473 for( uint i = 0; i < _cfg._num_blocks; i++ ) {
474 Block *b = _cfg._blocks[i];
475 // Clone (rather than smash in place) the liveout info, so it is alive
476 // for the "collect_gc_info" phase later.
501 // Reset block's register pressure values for each ifg construction
502 uint pressure[2], hrp_index[2];
503 pressure[0] = pressure[1] = 0;
504 hrp_index[0] = hrp_index[1] = last_inst+1;
505 b->_reg_pressure = b->_freg_pressure = 0;
506 // Liveout things are presumed live for the whole block. We accumulate
507 // 'area' accordingly. If they get killed in the block, we'll subtract
508 // the unused part of the block from the area.
509 int inst_count = last_inst - first_inst;
510 double cost = (inst_count <= 0) ? 0.0 : b->_freq * double(inst_count);
511 assert(!(cost < 0.0), "negative spill cost" );
512 IndexSetIterator elements(&liveout);
513 uint lidx;
514 while ((lidx = elements.next()) != 0) {
515 LRG &lrg = lrgs(lidx);
516 lrg._area += cost;
517 // Compute initial register pressure
518 if (lrg.mask().is_UP() && lrg.mask_size()) {
519 if (lrg._is_float || lrg._is_vector) { // Count float pressure
520 pressure[1] += lrg.reg_pressure();
521
522 if( pressure[1] > b->_freg_pressure )
523 b->_freg_pressure = pressure[1];
524
525 // Count int pressure, but do not count the SP, flags
526 } else if( lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {
527 pressure[0] += lrg.reg_pressure();
528
529 if( pressure[0] > b->_reg_pressure )
530 b->_reg_pressure = pressure[0];
531
532 }
533 }
534 }
535 assert( pressure[0] == count_int_pressure (&liveout), "" );
536 assert( pressure[1] == count_float_pressure(&liveout), "" );
537
538 // The IFG is built by a single reverse pass over each basic block.
539 // Starting with the known live-out set, we remove things that get
540 // defined and add things that become live (essentially executing one
541 // pass of a standard LIVE analysis). Just before a Node defines a value
542 // (and removes it from the live-ness set) that value is certainly live.
543 // The defined value interferes with everything currently live. The
544 // value is then removed from the live-ness set and it's inputs are added
545 // to the live-ness set.
546 uint j;
547 for( j = last_inst + 1; j > 1; j-- ) {
548 Node *n = b->_nodes[j - 1];
549
550 // Get value being defined
551 uint r = n2lidx(n);
564 // Could also be a flags-projection of a dead ADD or such.
565 (n2lidx(def) && !liveout.member(n2lidx(def)) ) ) {
566 b->_nodes.remove(j - 1);
567 if( lrgs(r)._def == n ) lrgs(r)._def = 0;
568 n->disconnect_inputs(NULL, C);
569 _cfg._bbs.map(n->_idx,NULL);
570 n->replace_by(C->top());
571 // Since yanking a Node from block, high pressure moves up one
572 hrp_index[0]--;
573 hrp_index[1]--;
574 continue;
575 }
576
577 // Fat-projections kill many registers which cannot be used to
578 // hold live ranges.
579 if( lrgs(r)._fat_proj ) {
580 // Count the int-only registers
581 RegMask itmp = lrgs(r).mask();
582 itmp.AND(*Matcher::idealreg2regmask[Op_RegI]);
583 int iregs = itmp.Size();
584
585 if( pressure[0]+iregs > b->_reg_pressure )
586 b->_reg_pressure = pressure[0]+iregs;
587
588 if( pressure[0] <= (uint)INTPRESSURE &&
589 pressure[0]+iregs > (uint)INTPRESSURE ) {
590 hrp_index[0] = j-1;
591 }
592 // Count the float-only registers
593 RegMask ftmp = lrgs(r).mask();
594 ftmp.AND(*Matcher::idealreg2regmask[Op_RegD]);
595 int fregs = ftmp.Size();
596
597 if( pressure[1]+fregs > b->_freg_pressure )
598 b->_freg_pressure = pressure[1]+fregs;
599
600 if( pressure[1] <= (uint)FLOATPRESSURE &&
601 pressure[1]+fregs > (uint)FLOATPRESSURE ) {
602 hrp_index[1] = j-1;
603 }
604 }
605
606 } else { // Else it is live
607 // A DEF also ends 'area' partway through the block.
608 lrgs(r)._area -= cost;
609 assert(!(lrgs(r)._area < 0.0), "negative spill area" );
610
611 // Insure high score for immediate-use spill copies so they get a color
612 if( n->is_SpillCopy()
613 && lrgs(r).is_singledef() // MultiDef live range can still split
614 && n->outcnt() == 1 // and use must be in this block
615 && _cfg._bbs[n->unique_out()->_idx] == b ) {
616 // All single-use MachSpillCopy(s) that immediately precede their
617 // use must color early. If a longer live range steals their
618 // color, the spill copy will split and may push another spill copy
619 // further away resulting in an infinite spill-split-retry cycle.
620 // Assigning a zero area results in a high score() and a good
621 // location in the simplify list.
738 // flag-setting behavior alive while also keeping the (useful)
739 // memory update effect.
740 for( uint k = ((n->Opcode() == Op_SCMemProj) ? 0:1); k < n->req(); k++ ) {
741 Node *def = n->in(k);
742 uint x = n2lidx(def);
743 if( !x ) continue;
744 LRG &lrg = lrgs(x);
745 // No use-side cost for spilling debug info
746 if( k < debug_start )
747 // A USE costs twice block frequency (once for the Load, once
748 // for a Load-delay). Rematerialized uses only cost once.
749 lrg._cost += (def->rematerialize() ? b->_freq : (b->_freq + b->_freq));
750 // It is live now
751 if( liveout.insert( x ) ) {
752 // Newly live things assumed live from here to top of block
753 lrg._area += cost;
754 // Adjust register pressure
755 if (lrg.mask().is_UP() && lrg.mask_size()) {
756 if (lrg._is_float || lrg._is_vector) {
757 pressure[1] += lrg.reg_pressure();
758
759 if( pressure[1] > b->_freg_pressure )
760 b->_freg_pressure = pressure[1];
761
762 } else if( lrg.mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {
763 pressure[0] += lrg.reg_pressure();
764
765 if( pressure[0] > b->_reg_pressure )
766 b->_reg_pressure = pressure[0];
767
768 }
769 }
770 assert( pressure[0] == count_int_pressure (&liveout), "" );
771 assert( pressure[1] == count_float_pressure(&liveout), "" );
772 }
773 assert(!(lrg._area < 0.0), "negative spill area" );
774 }
775 }
776 } // End of reverse pass over all instructions in block
777
778 // If we run off the top of the block with high pressure and
779 // never see a hi-to-low pressure transition, just record that
780 // the whole block is high pressure.
781 if( pressure[0] > (uint)INTPRESSURE ) {
782 hrp_index[0] = 0;
783
784 if( pressure[0] > b->_reg_pressure )
785 b->_reg_pressure = pressure[0];
786 }
787 if( pressure[1] > (uint)FLOATPRESSURE ) {
788 hrp_index[1] = 0;
789
790 if( pressure[1] > b->_freg_pressure )
791 b->_freg_pressure = pressure[1];
792 }
793
794 // Compute high pressure indice; avoid landing in the middle of projnodes
795 j = hrp_index[0];
796 if( j < b->_nodes.size() && j < b->end_idx()+1 ) {
797 Node *cur = b->_nodes[j];
798 while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) {
799 j--;
800 cur = b->_nodes[j];
801 }
802 }
803 b->_ihrp_index = j;
804 j = hrp_index[1];
805 if( j < b->_nodes.size() && j < b->end_idx()+1 ) {
806 Node *cur = b->_nodes[j];
807 while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) {
808 j--;
809 cur = b->_nodes[j];
810 }
811 }
|