60 else tty->print("? ");
61
62 if( is_multidef() ) {
63 tty->print("MultiDef ");
64 if (_defs != NULL) {
65 tty->print("(");
66 for (int i = 0; i < _defs->length(); i++) {
67 tty->print("N%d ", _defs->at(i)->_idx);
68 }
69 tty->print(") ");
70 }
71 }
72 else if( _def == 0 ) tty->print("Dead ");
73 else tty->print("Def: N%d ",_def->_idx);
74
75 tty->print("Cost:%4.2g Area:%4.2g Score:%4.2g ",_cost,_area, score());
76 // Flags
77 if( _is_oop ) tty->print("Oop ");
78 if( _is_float ) tty->print("Float ");
79 if( _is_vector ) tty->print("Vector ");
80 if( _was_spilled1 ) tty->print("Spilled ");
81 if( _was_spilled2 ) tty->print("Spilled2 ");
82 if( _direct_conflict ) tty->print("Direct_conflict ");
83 if( _fat_proj ) tty->print("Fat ");
84 if( _was_lo ) tty->print("Lo ");
85 if( _has_copy ) tty->print("Copy ");
86 if( _at_risk ) tty->print("Risk ");
87
88 if( _must_spill ) tty->print("Must_spill ");
89 if( _is_bound ) tty->print("Bound ");
90 if( _msize_valid ) {
91 if( _degree_valid && lo_degree() ) tty->print("Trivial ");
92 }
93
94 tty->cr();
95 }
96 #endif
97
98 // Compute score from cost and area. Low score is best to spill.
99 static double raw_score( double cost, double area ) {
627 if (C->failing()) {
628 return;
629 }
630
631 NOT_PRODUCT(C->verify_graph_edges();)
632
633 // Move important info out of the live_arena to longer lasting storage.
634 alloc_node_regs(_lrg_map.size());
635 for (uint i=0; i < _lrg_map.size(); i++) {
636 if (_lrg_map.live_range_id(i)) { // Live range associated with Node?
637 LRG &lrg = lrgs(_lrg_map.live_range_id(i));
638 if (!lrg.alive()) {
639 set_bad(i);
640 } else if (lrg.num_regs() == 1) {
641 set1(i, lrg.reg());
642 } else { // Must be a register-set
643 if (!lrg._fat_proj) { // Must be aligned adjacent register set
644 // Live ranges record the highest register in their mask.
645 // We want the low register for the AD file writer's convenience.
646 OptoReg::Name hi = lrg.reg(); // Get hi register
647 OptoReg::Name lo = OptoReg::add(hi, (1-lrg.num_regs())); // Find lo
648 // We have to use pair [lo,lo+1] even for wide vectors because
649 // the rest of code generation works only with pairs. It is safe
650 // since for registers encoding only 'lo' is used.
651 // Second reg from pair is used in ScheduleAndBundle on SPARC where
652 // vector max size is 8 which corresponds to registers pair.
653 // It is also used in BuildOopMaps but oop operations are not
654 // vectorized.
655 set2(i, lo);
656 } else { // Misaligned; extract 2 bits
657 OptoReg::Name hi = lrg.reg(); // Get hi register
658 lrg.Remove(hi); // Yank from mask
659 int lo = lrg.mask().find_first_elem(); // Find lo
660 set_pair(i, hi, lo);
661 }
662 }
663 if( lrg._is_oop ) _node_oops.set(i);
664 } else {
665 set_bad(i);
666 }
667 }
785 lrg._defs->append(n);
786 }
787 #endif
788
789 // Check for a single def LRG; these can spill nicely
790 // via rematerialization. Flag as NULL for no def found
791 // yet, or 'n' for single def or -1 for many defs.
792 lrg._def = lrg._def ? NodeSentinel : n;
793
794 // Limit result register mask to acceptable registers
795 const RegMask &rm = n->out_RegMask();
796 lrg.AND( rm );
797
798 uint ireg = n->ideal_reg();
799 assert( !n->bottom_type()->isa_oop_ptr() || ireg == Op_RegP,
800 "oops must be in Op_RegP's" );
801
802 // Check for vector live range (only if vector register is used).
803 // On SPARC vector uses RegD which could be misaligned so it is not
804 // processes as vector in RA.
805 if (RegMask::is_vector(ireg))
806 lrg._is_vector = 1;
807 assert(n_type->isa_vect() == NULL || lrg._is_vector || ireg == Op_RegD || ireg == Op_RegL,
808 "vector must be in vector registers");
809
810 // Check for bound register masks
811 const RegMask &lrgmask = lrg.mask();
812 if (lrgmask.is_bound(ireg)) {
813 lrg._is_bound = 1;
814 }
815
816 // Check for maximum frequency value
817 if (lrg._maxfreq < block->_freq) {
818 lrg._maxfreq = block->_freq;
819 }
820
821 // Check for oop-iness, or long/double
822 // Check for multi-kill projection
823 switch (ireg) {
824 case MachProjNode::fat_proj:
825 // Fat projections have size equal to number of registers killed
826 lrg.set_num_regs(rm.Size());
888 lrg.set_reg_pressure(1); // normally one value per register
889 #endif
890 // If this def of a double forces a mis-aligned double,
891 // flag as '_fat_proj' - really flag as allowing misalignment
892 // AND changes how we count interferences. A mis-aligned
893 // double can interfere with TWO aligned pairs, or effectively
894 // FOUR registers!
895 if (rm.is_misaligned_pair()) {
896 lrg._fat_proj = 1;
897 lrg._is_bound = 1;
898 }
899 break;
900 case Op_RegF:
901 case Op_RegI:
902 case Op_RegN:
903 case Op_RegFlags:
904 case 0: // not an ideal register
905 lrg.set_num_regs(1);
906 lrg.set_reg_pressure(1);
907 break;
908 case Op_VecS:
909 assert(Matcher::vector_size_supported(T_BYTE,4), "sanity");
910 assert(RegMask::num_registers(Op_VecS) == RegMask::SlotsPerVecS, "sanity");
911 lrg.set_num_regs(RegMask::SlotsPerVecS);
912 lrg.set_reg_pressure(1);
913 break;
914 case Op_VecD:
915 assert(Matcher::vector_size_supported(T_FLOAT,RegMask::SlotsPerVecD), "sanity");
916 assert(RegMask::num_registers(Op_VecD) == RegMask::SlotsPerVecD, "sanity");
917 assert(lrgmask.is_aligned_sets(RegMask::SlotsPerVecD), "vector should be aligned");
918 lrg.set_num_regs(RegMask::SlotsPerVecD);
919 lrg.set_reg_pressure(1);
920 break;
921 case Op_VecX:
922 assert(Matcher::vector_size_supported(T_FLOAT,RegMask::SlotsPerVecX), "sanity");
923 assert(RegMask::num_registers(Op_VecX) == RegMask::SlotsPerVecX, "sanity");
924 assert(lrgmask.is_aligned_sets(RegMask::SlotsPerVecX), "vector should be aligned");
925 lrg.set_num_regs(RegMask::SlotsPerVecX);
926 lrg.set_reg_pressure(1);
927 break;
1288 // in which XMMd is used by RA to represent such vectors. A double value
1289 // uses [XMM,XMMb] pairs and XMMb is used by RA for it.
1290 // The register mask uses largest bits set of overlapping register sets.
1291 // On x86 with AVX it uses 8 bits for each XMM registers set.
1292 //
1293 // The 'lrg' already has cleared-to-set register mask (done in Select()
1294 // before calling choose_color()). Passing mask.Member(reg) check above
1295 // indicates that the size (num_regs) of 'reg' set is less or equal to
1296 // 'lrg' set size.
1297 // For set size 1 any register which is member of 'lrg' mask is legal.
1298 if (lrg.num_regs()==1)
1299 return true;
1300 // For larger sets only an aligned register with the same set size is legal.
1301 int mask = lrg.num_regs()-1;
1302 if ((reg&mask) == mask)
1303 return true;
1304 }
1305 return false;
1306 }
1307
1308 // Choose a color using the biasing heuristic
1309 OptoReg::Name PhaseChaitin::bias_color( LRG &lrg, int chunk ) {
1310
1311 // Check for "at_risk" LRG's
1312 uint risk_lrg = _lrg_map.find(lrg._risk_bias);
1313 if (risk_lrg != 0 && !_ifg->neighbors(risk_lrg)->is_empty()) {
1314 // Walk the colored neighbors of the "at_risk" candidate
1315 // Choose a color which is both legal and already taken by a neighbor
1316 // of the "at_risk" candidate in order to improve the chances of the
1317 // "at_risk" candidate of coloring
1318 IndexSetIterator elements(_ifg->neighbors(risk_lrg));
1319 uint datum;
1320 while ((datum = elements.next()) != 0) {
1321 OptoReg::Name reg = lrgs(datum).reg();
1322 // If this LRG's register is legal for us, choose it
1323 if (is_legal_reg(lrg, reg, chunk))
1324 return reg;
1325 }
1326 }
1327
1328 uint copy_lrg = _lrg_map.find(lrg._copy_bias);
1329 if (copy_lrg != 0) {
1330 // If he has a color,
1331 if(!_ifg->_yanked->test(copy_lrg)) {
1332 OptoReg::Name reg = lrgs(copy_lrg).reg();
1333 // And it is legal for you,
1334 if (is_legal_reg(lrg, reg, chunk))
1335 return reg;
1336 } else if( chunk == 0 ) {
1337 // Choose a color which is legal for him
1338 RegMask tempmask = lrg.mask();
1339 tempmask.AND(lrgs(copy_lrg).mask());
1340 tempmask.clear_to_sets(lrg.num_regs());
1341 OptoReg::Name reg = tempmask.find_first_set(lrg.num_regs());
1342 if (OptoReg::is_valid(reg))
1343 return reg;
1344 }
1345 }
1346
1347 // If no bias info exists, just go with the register selection ordering
1348 if (lrg._is_vector || lrg.num_regs() == 2) {
1349 // Find an aligned set
1350 return OptoReg::add(lrg.mask().find_first_set(lrg.num_regs()),chunk);
1351 }
1352
1353 // CNC - Fun hack. Alternate 1st and 2nd selection. Enables post-allocate
1354 // copy removal to remove many more copies, by preventing a just-assigned
1355 // register from being repeatedly assigned.
1356 OptoReg::Name reg = lrg.mask().find_first_elem();
1357 if( (++_alternate & 1) && OptoReg::is_valid(reg) ) {
1358 // This 'Remove; find; Insert' idiom is an expensive way to find the
1359 // SECOND element in the mask.
1360 lrg.Remove(reg);
1361 OptoReg::Name reg2 = lrg.mask().find_first_elem();
1362 lrg.Insert(reg);
1363 if( OptoReg::is_reg(reg2))
1364 reg = reg2;
1365 }
1366 return OptoReg::add( reg, chunk );
1367 }
1368
1369 // Choose a color in the current chunk
1370 OptoReg::Name PhaseChaitin::choose_color( LRG &lrg, int chunk ) {
1385 assert( !chunk, "always color in 1st chunk" );
1386 // Return the highest element in the set.
1387 return lrg.mask().find_last_elem();
1388 }
1389
1390 // Select colors by re-inserting LRGs back into the IFG. LRGs are re-inserted
1391 // in reverse order of removal. As long as nothing of hi-degree was yanked,
1392 // everything going back is guaranteed a color. Select that color. If some
1393 // hi-degree LRG cannot get a color then we record that we must spill.
1394 uint PhaseChaitin::Select( ) {
1395 Compile::TracePhase tp("chaitinSelect", &timers[_t_chaitinSelect]);
1396
1397 uint spill_reg = LRG::SPILL_REG;
1398 _max_reg = OptoReg::Name(0); // Past max register used
1399 while( _simplified ) {
1400 // Pull next LRG from the simplified list - in reverse order of removal
1401 uint lidx = _simplified;
1402 LRG *lrg = &lrgs(lidx);
1403 _simplified = lrg->_next;
1404
1405
1406 #ifndef PRODUCT
1407 if (trace_spilling()) {
1408 ttyLocker ttyl;
1409 tty->print_cr("L%d selecting degree %d degrees_of_freedom %d", lidx, lrg->degree(),
1410 lrg->degrees_of_freedom());
1411 lrg->dump();
1412 }
1413 #endif
1414
1415 // Re-insert into the IFG
1416 _ifg->re_insert(lidx);
1417 if( !lrg->alive() ) continue;
1418 // capture allstackedness flag before mask is hacked
1419 const int is_allstack = lrg->mask().is_AllStack();
1420
1421 // Yeah, yeah, yeah, I know, I know. I can refactor this
1422 // to avoid the GOTO, although the refactored code will not
1423 // be much clearer. We arrive here IFF we have a stack-based
1424 // live range that cannot color in the current chunk, and it
1425 // has to move into the next free stack chunk.
1467 }
1468 }
1469 }
1470 //assert(is_allstack == lrg->mask().is_AllStack(), "nbrs must not change AllStackedness");
1471 // Aligned pairs need aligned masks
1472 assert(!lrg->_is_vector || !lrg->_fat_proj, "sanity");
1473 if (lrg->num_regs() > 1 && !lrg->_fat_proj) {
1474 lrg->clear_to_sets();
1475 }
1476
1477 // Check if a color is available and if so pick the color
1478 OptoReg::Name reg = choose_color( *lrg, chunk );
1479
1480 //---------------
1481 // If we fail to color and the AllStack flag is set, trigger
1482 // a chunk-rollover event
1483 if(!OptoReg::is_valid(OptoReg::add(reg,-chunk)) && is_allstack) {
1484 // Bump register mask up to next stack chunk
1485 chunk += RegMask::CHUNK_SIZE;
1486 lrg->Set_All();
1487
1488 goto retry_next_chunk;
1489 }
1490
1491 //---------------
1492 // Did we get a color?
1493 else if( OptoReg::is_valid(reg)) {
1494 #ifndef PRODUCT
1495 RegMask avail_rm = lrg->mask();
1496 #endif
1497
1498 // Record selected register
1499 lrg->set_reg(reg);
1500
1501 if( reg >= _max_reg ) // Compute max register limit
1502 _max_reg = OptoReg::add(reg,1);
1503 // Fold reg back into normal space
1504 reg = OptoReg::add(reg,-chunk);
1505
1506 // If the live range is not bound, then we actually had some choices
1507 // to make. In this case, the mask has more bits in it than the colors
1508 // chosen. Restrict the mask to just what was picked.
1509 int n_regs = lrg->num_regs();
1510 assert(!lrg->_is_vector || !lrg->_fat_proj, "sanity");
1511 if (n_regs == 1 || !lrg->_fat_proj) {
1512 assert(!lrg->_is_vector || n_regs <= RegMask::SlotsPerVecZ, "sanity");
1513 lrg->Clear(); // Clear the mask
1514 lrg->Insert(reg); // Set regmask to match selected reg
1515 // For vectors and pairs, also insert the low bit of the pair
1516 for (int i = 1; i < n_regs; i++)
1517 lrg->Insert(OptoReg::add(reg,-i));
1518 lrg->set_mask_size(n_regs);
1519 } else { // Else fatproj
1520 // mask must be equal to fatproj bits, by definition
1521 }
1522 #ifndef PRODUCT
1523 if (trace_spilling()) {
1524 ttyLocker ttyl;
1525 tty->print("L%d selected ", lidx);
1526 lrg->mask().dump();
1527 tty->print(" from ");
1528 avail_rm.dump();
1529 tty->cr();
1530 }
1531 #endif
1532 // Note that reg is the highest-numbered register in the newly-bound mask.
1533 } // end color available case
1534
1535 //---------------
1536 // Live range is live and no colors available
1537 else {
|
60 else tty->print("? ");
61
62 if( is_multidef() ) {
63 tty->print("MultiDef ");
64 if (_defs != NULL) {
65 tty->print("(");
66 for (int i = 0; i < _defs->length(); i++) {
67 tty->print("N%d ", _defs->at(i)->_idx);
68 }
69 tty->print(") ");
70 }
71 }
72 else if( _def == 0 ) tty->print("Dead ");
73 else tty->print("Def: N%d ",_def->_idx);
74
75 tty->print("Cost:%4.2g Area:%4.2g Score:%4.2g ",_cost,_area, score());
76 // Flags
77 if( _is_oop ) tty->print("Oop ");
78 if( _is_float ) tty->print("Float ");
79 if( _is_vector ) tty->print("Vector ");
80 if( _is_scalable ) tty->print("Scalable ");
81 if( _was_spilled1 ) tty->print("Spilled ");
82 if( _was_spilled2 ) tty->print("Spilled2 ");
83 if( _direct_conflict ) tty->print("Direct_conflict ");
84 if( _fat_proj ) tty->print("Fat ");
85 if( _was_lo ) tty->print("Lo ");
86 if( _has_copy ) tty->print("Copy ");
87 if( _at_risk ) tty->print("Risk ");
88
89 if( _must_spill ) tty->print("Must_spill ");
90 if( _is_bound ) tty->print("Bound ");
91 if( _msize_valid ) {
92 if( _degree_valid && lo_degree() ) tty->print("Trivial ");
93 }
94
95 tty->cr();
96 }
97 #endif
98
99 // Compute score from cost and area. Low score is best to spill.
100 static double raw_score( double cost, double area ) {
628 if (C->failing()) {
629 return;
630 }
631
632 NOT_PRODUCT(C->verify_graph_edges();)
633
634 // Move important info out of the live_arena to longer lasting storage.
635 alloc_node_regs(_lrg_map.size());
636 for (uint i=0; i < _lrg_map.size(); i++) {
637 if (_lrg_map.live_range_id(i)) { // Live range associated with Node?
638 LRG &lrg = lrgs(_lrg_map.live_range_id(i));
639 if (!lrg.alive()) {
640 set_bad(i);
641 } else if (lrg.num_regs() == 1) {
642 set1(i, lrg.reg());
643 } else { // Must be a register-set
644 if (!lrg._fat_proj) { // Must be aligned adjacent register set
645 // Live ranges record the highest register in their mask.
646 // We want the low register for the AD file writer's convenience.
647 OptoReg::Name hi = lrg.reg(); // Get hi register
648 int num_regs = lrg.num_regs();
649 if (lrg.is_scalable() && OptoReg::is_stack(hi)) {
650 // For scalable vector registers, when they are allocated in physical
651 // registers, num_regs is RegMask::SlotsPerVecA for reg mask of scalable
652 // vector. If they are allocated on stack, we need to get the actual
653 // num_regs, which reflects the physical length of scalable registers.
654 num_regs = lrg.scalable_reg_slots();
655 }
656 OptoReg::Name lo = OptoReg::add(hi, (1-num_regs)); // Find lo
657 // We have to use pair [lo,lo+1] even for wide vectors because
658 // the rest of code generation works only with pairs. It is safe
659 // since for registers encoding only 'lo' is used.
660 // Second reg from pair is used in ScheduleAndBundle on SPARC where
661 // vector max size is 8 which corresponds to registers pair.
662 // It is also used in BuildOopMaps but oop operations are not
663 // vectorized.
664 set2(i, lo);
665 } else { // Misaligned; extract 2 bits
666 OptoReg::Name hi = lrg.reg(); // Get hi register
667 lrg.Remove(hi); // Yank from mask
668 int lo = lrg.mask().find_first_elem(); // Find lo
669 set_pair(i, hi, lo);
670 }
671 }
672 if( lrg._is_oop ) _node_oops.set(i);
673 } else {
674 set_bad(i);
675 }
676 }
794 lrg._defs->append(n);
795 }
796 #endif
797
798 // Check for a single def LRG; these can spill nicely
799 // via rematerialization. Flag as NULL for no def found
800 // yet, or 'n' for single def or -1 for many defs.
801 lrg._def = lrg._def ? NodeSentinel : n;
802
803 // Limit result register mask to acceptable registers
804 const RegMask &rm = n->out_RegMask();
805 lrg.AND( rm );
806
807 uint ireg = n->ideal_reg();
808 assert( !n->bottom_type()->isa_oop_ptr() || ireg == Op_RegP,
809 "oops must be in Op_RegP's" );
810
811 // Check for vector live range (only if vector register is used).
812 // On SPARC vector uses RegD which could be misaligned so it is not
813 // processes as vector in RA.
814 if (RegMask::is_vector(ireg)) {
815 lrg._is_vector = 1;
816 if (ireg == Op_VecA) {
817 assert(Matcher::supports_scalable_vector(), "scalable vector should be supported");
818 lrg._is_scalable = 1;
819 // For scalable vector, when it is allocated in physical register,
820 // num_regs is RegMask::SlotsPerVecA for reg mask,
821 // which may not be the actual physical register size.
822 // If it is allocated in stack, we need to get the actual
823 // physical length of scalable vector register.
824 lrg.set_scalable_reg_slots(Matcher::scalable_vector_reg_size(T_FLOAT));
825 }
826 }
827 assert(n_type->isa_vect() == NULL || lrg._is_vector || ireg == Op_RegD || ireg == Op_RegL,
828 "vector must be in vector registers");
829
830 // Check for bound register masks
831 const RegMask &lrgmask = lrg.mask();
832 if (lrgmask.is_bound(ireg)) {
833 lrg._is_bound = 1;
834 }
835
836 // Check for maximum frequency value
837 if (lrg._maxfreq < block->_freq) {
838 lrg._maxfreq = block->_freq;
839 }
840
841 // Check for oop-iness, or long/double
842 // Check for multi-kill projection
843 switch (ireg) {
844 case MachProjNode::fat_proj:
845 // Fat projections have size equal to number of registers killed
846 lrg.set_num_regs(rm.Size());
908 lrg.set_reg_pressure(1); // normally one value per register
909 #endif
910 // If this def of a double forces a mis-aligned double,
911 // flag as '_fat_proj' - really flag as allowing misalignment
912 // AND changes how we count interferences. A mis-aligned
913 // double can interfere with TWO aligned pairs, or effectively
914 // FOUR registers!
915 if (rm.is_misaligned_pair()) {
916 lrg._fat_proj = 1;
917 lrg._is_bound = 1;
918 }
919 break;
920 case Op_RegF:
921 case Op_RegI:
922 case Op_RegN:
923 case Op_RegFlags:
924 case 0: // not an ideal register
925 lrg.set_num_regs(1);
926 lrg.set_reg_pressure(1);
927 break;
928 case Op_VecA:
929 assert(Matcher::supports_scalable_vector(), "does not support scalable vector");
930 assert(RegMask::num_registers(Op_VecA) == RegMask::SlotsPerVecA, "sanity");
931 assert(lrgmask.is_aligned_sets(RegMask::SlotsPerVecA), "vector should be aligned");
932 lrg.set_num_regs(RegMask::SlotsPerVecA);
933 lrg.set_reg_pressure(1);
934 break;
935 case Op_VecS:
936 assert(Matcher::vector_size_supported(T_BYTE,4), "sanity");
937 assert(RegMask::num_registers(Op_VecS) == RegMask::SlotsPerVecS, "sanity");
938 lrg.set_num_regs(RegMask::SlotsPerVecS);
939 lrg.set_reg_pressure(1);
940 break;
941 case Op_VecD:
942 assert(Matcher::vector_size_supported(T_FLOAT,RegMask::SlotsPerVecD), "sanity");
943 assert(RegMask::num_registers(Op_VecD) == RegMask::SlotsPerVecD, "sanity");
944 assert(lrgmask.is_aligned_sets(RegMask::SlotsPerVecD), "vector should be aligned");
945 lrg.set_num_regs(RegMask::SlotsPerVecD);
946 lrg.set_reg_pressure(1);
947 break;
948 case Op_VecX:
949 assert(Matcher::vector_size_supported(T_FLOAT,RegMask::SlotsPerVecX), "sanity");
950 assert(RegMask::num_registers(Op_VecX) == RegMask::SlotsPerVecX, "sanity");
951 assert(lrgmask.is_aligned_sets(RegMask::SlotsPerVecX), "vector should be aligned");
952 lrg.set_num_regs(RegMask::SlotsPerVecX);
953 lrg.set_reg_pressure(1);
954 break;
1315 // in which XMMd is used by RA to represent such vectors. A double value
1316 // uses [XMM,XMMb] pairs and XMMb is used by RA for it.
1317 // The register mask uses largest bits set of overlapping register sets.
1318 // On x86 with AVX it uses 8 bits for each XMM registers set.
1319 //
1320 // The 'lrg' already has cleared-to-set register mask (done in Select()
1321 // before calling choose_color()). Passing mask.Member(reg) check above
1322 // indicates that the size (num_regs) of 'reg' set is less or equal to
1323 // 'lrg' set size.
1324 // For set size 1 any register which is member of 'lrg' mask is legal.
1325 if (lrg.num_regs()==1)
1326 return true;
1327 // For larger sets only an aligned register with the same set size is legal.
1328 int mask = lrg.num_regs()-1;
1329 if ((reg&mask) == mask)
1330 return true;
1331 }
1332 return false;
1333 }
1334
1335 static OptoReg::Name find_first_set(LRG &lrg, RegMask mask, int chunk) {
1336 int num_regs = lrg.num_regs();
1337 OptoReg::Name assigned = mask.find_first_set(lrg, num_regs);
1338
1339 if (lrg.is_scalable()) {
1340 // a physical register is found
1341 if (chunk == 0 && OptoReg::is_reg(assigned)) {
1342 return assigned;
1343 }
1344
1345 // find available stack slots for scalable register
1346 if (lrg._is_vector) {
1347 num_regs = lrg.scalable_reg_slots();
1348 // if actual scalable vector register is exactly SlotsPerVecA * 32 bits
1349 if (num_regs == RegMask::SlotsPerVecA) {
1350 return assigned;
1351 }
1352
1353 // mask has been cleared out by clear_to_sets(SlotsPerVecA) before choose_color, but it
1354 // does not work for scalable size. We have to find adjacent scalable_reg_slots() bits
1355 // instead of SlotsPerVecA bits.
1356 assigned = mask.find_first_set(lrg, num_regs); // find highest valid reg
1357 while (OptoReg::is_valid(assigned) && RegMask::can_represent(assigned)) {
1358 // Verify the found reg has scalable_reg_slots() bits set.
1359 if (mask.is_valid_reg(assigned, num_regs)) {
1360 return assigned;
1361 } else {
1362 // Remove more for each iteration
1363 mask.Remove(assigned - num_regs + 1); // Unmask the lowest reg
1364 mask.clear_to_sets(RegMask::SlotsPerVecA); // Align by SlotsPerVecA bits
1365 assigned = mask.find_first_set(lrg, num_regs);
1366 }
1367 }
1368 return OptoReg::Bad; // will cause chunk change, and retry next chunk
1369 }
1370 }
1371
1372 return assigned;
1373 }
1374
1375 // Choose a color using the biasing heuristic
1376 OptoReg::Name PhaseChaitin::bias_color( LRG &lrg, int chunk ) {
1377
1378 // Check for "at_risk" LRG's
1379 uint risk_lrg = _lrg_map.find(lrg._risk_bias);
1380 if (risk_lrg != 0 && !_ifg->neighbors(risk_lrg)->is_empty()) {
1381 // Walk the colored neighbors of the "at_risk" candidate
1382 // Choose a color which is both legal and already taken by a neighbor
1383 // of the "at_risk" candidate in order to improve the chances of the
1384 // "at_risk" candidate of coloring
1385 IndexSetIterator elements(_ifg->neighbors(risk_lrg));
1386 uint datum;
1387 while ((datum = elements.next()) != 0) {
1388 OptoReg::Name reg = lrgs(datum).reg();
1389 // If this LRG's register is legal for us, choose it
1390 if (is_legal_reg(lrg, reg, chunk))
1391 return reg;
1392 }
1393 }
1394
1395 uint copy_lrg = _lrg_map.find(lrg._copy_bias);
1396 if (copy_lrg != 0) {
1397 // If he has a color,
1398 if(!_ifg->_yanked->test(copy_lrg)) {
1399 OptoReg::Name reg = lrgs(copy_lrg).reg();
1400 // And it is legal for you,
1401 if (is_legal_reg(lrg, reg, chunk))
1402 return reg;
1403 } else if( chunk == 0 ) {
1404 // Choose a color which is legal for him
1405 RegMask tempmask = lrg.mask();
1406 tempmask.AND(lrgs(copy_lrg).mask());
1407 tempmask.clear_to_sets(lrg.num_regs());
1408 OptoReg::Name reg = find_first_set(lrg, tempmask, chunk);
1409 if (OptoReg::is_valid(reg))
1410 return reg;
1411 }
1412 }
1413
1414 // If no bias info exists, just go with the register selection ordering
1415 if (lrg._is_vector || lrg.num_regs() == 2) {
1416 // Find an aligned set
1417 return OptoReg::add(find_first_set(lrg, lrg.mask(), chunk), chunk);
1418 }
1419
1420 // CNC - Fun hack. Alternate 1st and 2nd selection. Enables post-allocate
1421 // copy removal to remove many more copies, by preventing a just-assigned
1422 // register from being repeatedly assigned.
1423 OptoReg::Name reg = lrg.mask().find_first_elem();
1424 if( (++_alternate & 1) && OptoReg::is_valid(reg) ) {
1425 // This 'Remove; find; Insert' idiom is an expensive way to find the
1426 // SECOND element in the mask.
1427 lrg.Remove(reg);
1428 OptoReg::Name reg2 = lrg.mask().find_first_elem();
1429 lrg.Insert(reg);
1430 if( OptoReg::is_reg(reg2))
1431 reg = reg2;
1432 }
1433 return OptoReg::add( reg, chunk );
1434 }
1435
1436 // Choose a color in the current chunk
1437 OptoReg::Name PhaseChaitin::choose_color( LRG &lrg, int chunk ) {
1452 assert( !chunk, "always color in 1st chunk" );
1453 // Return the highest element in the set.
1454 return lrg.mask().find_last_elem();
1455 }
1456
1457 // Select colors by re-inserting LRGs back into the IFG. LRGs are re-inserted
1458 // in reverse order of removal. As long as nothing of hi-degree was yanked,
1459 // everything going back is guaranteed a color. Select that color. If some
1460 // hi-degree LRG cannot get a color then we record that we must spill.
1461 uint PhaseChaitin::Select( ) {
1462 Compile::TracePhase tp("chaitinSelect", &timers[_t_chaitinSelect]);
1463
1464 uint spill_reg = LRG::SPILL_REG;
1465 _max_reg = OptoReg::Name(0); // Past max register used
1466 while( _simplified ) {
1467 // Pull next LRG from the simplified list - in reverse order of removal
1468 uint lidx = _simplified;
1469 LRG *lrg = &lrgs(lidx);
1470 _simplified = lrg->_next;
1471
1472 #ifndef PRODUCT
1473 if (trace_spilling()) {
1474 ttyLocker ttyl;
1475 tty->print_cr("L%d selecting degree %d degrees_of_freedom %d", lidx, lrg->degree(),
1476 lrg->degrees_of_freedom());
1477 lrg->dump();
1478 }
1479 #endif
1480
1481 // Re-insert into the IFG
1482 _ifg->re_insert(lidx);
1483 if( !lrg->alive() ) continue;
1484 // capture allstackedness flag before mask is hacked
1485 const int is_allstack = lrg->mask().is_AllStack();
1486
1487 // Yeah, yeah, yeah, I know, I know. I can refactor this
1488 // to avoid the GOTO, although the refactored code will not
1489 // be much clearer. We arrive here IFF we have a stack-based
1490 // live range that cannot color in the current chunk, and it
1491 // has to move into the next free stack chunk.
1533 }
1534 }
1535 }
1536 //assert(is_allstack == lrg->mask().is_AllStack(), "nbrs must not change AllStackedness");
1537 // Aligned pairs need aligned masks
1538 assert(!lrg->_is_vector || !lrg->_fat_proj, "sanity");
1539 if (lrg->num_regs() > 1 && !lrg->_fat_proj) {
1540 lrg->clear_to_sets();
1541 }
1542
1543 // Check if a color is available and if so pick the color
1544 OptoReg::Name reg = choose_color( *lrg, chunk );
1545
1546 //---------------
1547 // If we fail to color and the AllStack flag is set, trigger
1548 // a chunk-rollover event
1549 if(!OptoReg::is_valid(OptoReg::add(reg,-chunk)) && is_allstack) {
1550 // Bump register mask up to next stack chunk
1551 chunk += RegMask::CHUNK_SIZE;
1552 lrg->Set_All();
1553 goto retry_next_chunk;
1554 }
1555
1556 //---------------
1557 // Did we get a color?
1558 else if( OptoReg::is_valid(reg)) {
1559 #ifndef PRODUCT
1560 RegMask avail_rm = lrg->mask();
1561 #endif
1562
1563 // Record selected register
1564 lrg->set_reg(reg);
1565
1566 if( reg >= _max_reg ) // Compute max register limit
1567 _max_reg = OptoReg::add(reg,1);
1568 // Fold reg back into normal space
1569 reg = OptoReg::add(reg,-chunk);
1570
1571 // If the live range is not bound, then we actually had some choices
1572 // to make. In this case, the mask has more bits in it than the colors
1573 // chosen. Restrict the mask to just what was picked.
1574 int n_regs = lrg->num_regs();
1575 assert(!lrg->_is_vector || !lrg->_fat_proj, "sanity");
1576 if (n_regs == 1 || !lrg->_fat_proj) {
1577 if (Matcher::supports_scalable_vector()) {
1578 assert(!lrg->_is_vector || n_regs <= RegMask::SlotsPerVecA, "sanity");
1579 } else {
1580 assert(!lrg->_is_vector || n_regs <= RegMask::SlotsPerVecZ, "sanity");
1581 }
1582 lrg->Clear(); // Clear the mask
1583 lrg->Insert(reg); // Set regmask to match selected reg
1584 // For vectors and pairs, also insert the low bit of the pair
1585 // We always choose the high bit, then mask the low bits by register size
1586 if (lrg->is_scalable() && OptoReg::is_stack(lrg->reg())) { // stack
1587 n_regs = lrg->scalable_reg_slots();
1588 }
1589 for (int i = 1; i < n_regs; i++) {
1590 lrg->Insert(OptoReg::add(reg,-i));
1591 }
1592 lrg->set_mask_size(n_regs);
1593 } else { // Else fatproj
1594 // mask must be equal to fatproj bits, by definition
1595 }
1596 #ifndef PRODUCT
1597 if (trace_spilling()) {
1598 ttyLocker ttyl;
1599 tty->print("L%d selected ", lidx);
1600 lrg->mask().dump();
1601 tty->print(" from ");
1602 avail_rm.dump();
1603 tty->cr();
1604 }
1605 #endif
1606 // Note that reg is the highest-numbered register in the newly-bound mask.
1607 } // end color available case
1608
1609 //---------------
1610 // Live range is live and no colors available
1611 else {
|