58 if( _degree_valid ) tty->print( "%d ", _eff_degree );
59 else tty->print("? ");
60
61 if( is_multidef() ) {
62 tty->print("MultiDef ");
63 if (_defs != NULL) {
64 tty->print("(");
65 for (int i = 0; i < _defs->length(); i++) {
66 tty->print("N%d ", _defs->at(i)->_idx);
67 }
68 tty->print(") ");
69 }
70 }
71 else if( _def == 0 ) tty->print("Dead ");
72 else tty->print("Def: N%d ",_def->_idx);
73
74 tty->print("Cost:%4.2g Area:%4.2g Score:%4.2g ",_cost,_area, score());
75 // Flags
76 if( _is_oop ) tty->print("Oop ");
77 if( _is_float ) tty->print("Float ");
78 if( _was_spilled1 ) tty->print("Spilled ");
79 if( _was_spilled2 ) tty->print("Spilled2 ");
80 if( _direct_conflict ) tty->print("Direct_conflict ");
81 if( _fat_proj ) tty->print("Fat ");
82 if( _was_lo ) tty->print("Lo ");
83 if( _has_copy ) tty->print("Copy ");
84 if( _at_risk ) tty->print("Risk ");
85
86 if( _must_spill ) tty->print("Must_spill ");
87 if( _is_bound ) tty->print("Bound ");
88 if( _msize_valid ) {
89 if( _degree_valid && lo_degree() ) tty->print("Trivial ");
90 }
91
92 tty->cr();
93 }
94 #endif
95
96 //------------------------------score------------------------------------------
97 // Compute score from cost and area. Low score is best to spill.
462 _total_framesize += _framesize;
463 if( (int)_framesize > _max_framesize )
464 _max_framesize = _framesize;
465 #endif
466
467 // Convert CISC spills
468 fixup_spills();
469
470 // Log regalloc results
471 CompileLog* log = Compile::current()->log();
472 if (log != NULL) {
473 log->elem("regalloc attempts='%d' success='%d'", _trip_cnt, !C->failing());
474 }
475
476 if (C->failing()) return;
477
478 NOT_PRODUCT( C->verify_graph_edges(); )
479
480 // Move important info out of the live_arena to longer lasting storage.
481 alloc_node_regs(_names.Size());
482 for( uint i=0; i < _names.Size(); i++ ) {
483 if( _names[i] ) { // Live range associated with Node?
484 LRG &lrg = lrgs( _names[i] );
485 if( lrg.num_regs() == 1 ) {
486 _node_regs[i].set1( lrg.reg() );
487 } else { // Must be a register-pair
488 if( !lrg._fat_proj ) { // Must be aligned adjacent register pair
489 // Live ranges record the highest register in their mask.
490 // We want the low register for the AD file writer's convenience.
491 _node_regs[i].set2( OptoReg::add(lrg.reg(),-1) );
492 } else { // Misaligned; extract 2 bits
493 OptoReg::Name hi = lrg.reg(); // Get hi register
494 lrg.Remove(hi); // Yank from mask
495 int lo = lrg.mask().find_first_elem(); // Find lo
496 _node_regs[i].set_pair( hi, lo );
497 }
498 }
499 if( lrg._is_oop ) _node_oops.set(i);
500 } else {
501 _node_regs[i].set_bad();
502 }
503 }
504
505 // Done!
506 _live = NULL;
507 _ifg = NULL;
508 C->set_indexSet_arena(NULL); // ResourceArea is at end of scope
509 }
510
511 //------------------------------de_ssa-----------------------------------------
551 uint input_edge_start =1; // Skip control most nodes
552 if( n->is_Mach() ) input_edge_start = n->as_Mach()->oper_input_base();
553 uint idx = n->is_Copy();
554
555 // Get virtual register number, same as LiveRanGe index
556 uint vreg = n2lidx(n);
557 LRG &lrg = lrgs(vreg);
558 if( vreg ) { // No vreg means un-allocable (e.g. memory)
559
560 // Collect has-copy bit
561 if( idx ) {
562 lrg._has_copy = 1;
563 uint clidx = n2lidx(n->in(idx));
564 LRG ©_src = lrgs(clidx);
565 copy_src._has_copy = 1;
566 }
567
568 // Check for float-vs-int live range (used in register-pressure
569 // calculations)
570 const Type *n_type = n->bottom_type();
571 if( n_type->is_floatingpoint() )
572 lrg._is_float = 1;
573
574 // Check for twice prior spilling. Once prior spilling might have
575 // spilled 'soft', 2nd prior spill should have spilled 'hard' and
576 // further spilling is unlikely to make progress.
577 if( _spilled_once.test(n->_idx) ) {
578 lrg._was_spilled1 = 1;
579 if( _spilled_twice.test(n->_idx) )
580 lrg._was_spilled2 = 1;
581 }
582
583 #ifndef PRODUCT
584 if (trace_spilling() && lrg._def != NULL) {
585 // collect defs for MultiDef printing
586 if (lrg._defs == NULL) {
587 lrg._defs = new (_ifg->_arena) GrowableArray<Node*>(_ifg->_arena, 2, 0, NULL);
588 lrg._defs->append(lrg._def);
589 }
590 lrg._defs->append(n);
591 }
592 #endif
593
594 // Check for a single def LRG; these can spill nicely
595 // via rematerialization. Flag as NULL for no def found
596 // yet, or 'n' for single def or -1 for many defs.
597 lrg._def = lrg._def ? NodeSentinel : n;
598
599 // Limit result register mask to acceptable registers
600 const RegMask &rm = n->out_RegMask();
601 lrg.AND( rm );
602 // Check for bound register masks
603 const RegMask &lrgmask = lrg.mask();
604 if( lrgmask.is_bound1() || lrgmask.is_bound2() )
605 lrg._is_bound = 1;
606
607 // Check for maximum frequency value
608 if( lrg._maxfreq < b->_freq )
609 lrg._maxfreq = b->_freq;
610
611 int ireg = n->ideal_reg();
612 assert( !n->bottom_type()->isa_oop_ptr() || ireg == Op_RegP,
613 "oops must be in Op_RegP's" );
614 // Check for oop-iness, or long/double
615 // Check for multi-kill projection
616 switch( ireg ) {
617 case MachProjNode::fat_proj:
618 // Fat projections have size equal to number of registers killed
619 lrg.set_num_regs(rm.Size());
620 lrg.set_reg_pressure(lrg.num_regs());
621 lrg._fat_proj = 1;
622 lrg._is_bound = 1;
623 break;
624 case Op_RegP:
625 #ifdef _LP64
626 lrg.set_num_regs(2); // Size is 2 stack words
627 #else
628 lrg.set_num_regs(1); // Size is 1 stack word
629 #endif
630 // Register pressure is tracked relative to the maximum values
631 // suggested for that platform, INTPRESSURE and FLOATPRESSURE,
632 // and relative to other types which compete for the same regs.
633 //
672 case Op_RegL: // Check for long or double
673 case Op_RegD:
674 lrg.set_num_regs(2);
675 // Define platform specific register pressure
676 #if defined(SPARC) || defined(ARM)
677 lrg.set_reg_pressure(2);
678 #elif defined(IA32)
679 if( ireg == Op_RegL ) {
680 lrg.set_reg_pressure(2);
681 } else {
682 lrg.set_reg_pressure(1);
683 }
684 #else
685 lrg.set_reg_pressure(1); // normally one value per register
686 #endif
687 // If this def of a double forces a mis-aligned double,
688 // flag as '_fat_proj' - really flag as allowing misalignment
689 // AND changes how we count interferences. A mis-aligned
690 // double can interfere with TWO aligned pairs, or effectively
691 // FOUR registers!
692 if( rm.is_misaligned_Pair() ) {
693 lrg._fat_proj = 1;
694 lrg._is_bound = 1;
695 }
696 break;
697 case Op_RegF:
698 case Op_RegI:
699 case Op_RegN:
700 case Op_RegFlags:
701 case 0: // not an ideal register
702 lrg.set_num_regs(1);
703 #ifdef SPARC
704 lrg.set_reg_pressure(2);
705 #else
706 lrg.set_reg_pressure(1);
707 #endif
708 break;
709 default:
710 ShouldNotReachHere();
711 }
712 }
713
714 // Now do the same for inputs
715 uint cnt = n->req();
716 // Setup for CISC SPILLING
717 uint inp = (uint)AdlcVMDeps::Not_cisc_spillable;
718 if( UseCISCSpill && after_aggressive ) {
719 inp = n->cisc_operand();
720 if( inp != (uint)AdlcVMDeps::Not_cisc_spillable )
721 // Convert operand number to edge index number
722 inp = n->as_Mach()->operand_index(inp);
723 }
724 // Prepare register mask for each input
725 for( uint k = input_edge_start; k < cnt; k++ ) {
726 uint vreg = n2lidx(n->in(k));
727 if( !vreg ) continue;
728
746 // int op = m->ideal_Opcode();
747 // if (n->is_Call() && (op == Op_AddF || op == Op_MulF) ) {
748 // int zzz = 1;
749 // }
750 // }
751
752 // Limit result register mask to acceptable registers.
753 // Do not limit registers from uncommon uses before
754 // AggressiveCoalesce. This effectively pre-virtual-splits
755 // around uncommon uses of common defs.
756 const RegMask &rm = n->in_RegMask(k);
757 if( !after_aggressive &&
758 _cfg._bbs[n->in(k)->_idx]->_freq > 1000*b->_freq ) {
759 // Since we are BEFORE aggressive coalesce, leave the register
760 // mask untrimmed by the call. This encourages more coalescing.
761 // Later, AFTER aggressive, this live range will have to spill
762 // but the spiller handles slow-path calls very nicely.
763 } else {
764 lrg.AND( rm );
765 }
766 // Check for bound register masks
767 const RegMask &lrgmask = lrg.mask();
768 if( lrgmask.is_bound1() || lrgmask.is_bound2() )
769 lrg._is_bound = 1;
770 // If this use of a double forces a mis-aligned double,
771 // flag as '_fat_proj' - really flag as allowing misalignment
772 // AND changes how we count interferences. A mis-aligned
773 // double can interfere with TWO aligned pairs, or effectively
774 // FOUR registers!
775 if( lrg.num_regs() == 2 && !lrg._fat_proj && rm.is_misaligned_Pair() ) {
776 lrg._fat_proj = 1;
777 lrg._is_bound = 1;
778 }
779 // if the LRG is an unaligned pair, we will have to spill
780 // so clear the LRG's register mask if it is not already spilled
781 if ( !n->is_SpillCopy() &&
782 (lrg._def == NULL || lrg.is_multidef() || !lrg._def->is_SpillCopy()) &&
783 lrgmask.is_misaligned_Pair()) {
784 lrg.Clear();
785 }
786
787 // Check for maximum frequency value
788 if( lrg._maxfreq < b->_freq )
789 lrg._maxfreq = b->_freq;
790
791 } // End for all allocated inputs
792 } // end for all instructions
793 } // end for all blocks
794
795 // Final per-liverange setup
796 for( uint i2=0; i2<_maxlrg; i2++ ) {
797 LRG &lrg = lrgs(i2);
798 if( lrg.num_regs() == 2 && !lrg._fat_proj )
799 lrg.ClearToPairs();
800 lrg.compute_set_mask_size();
801 if( lrg.not_free() ) { // Handle case where we lose from the start
802 lrg.set_reg(OptoReg::Name(LRG::SPILL_REG));
803 lrg._direct_conflict = 1;
804 }
805 lrg.set_degree(0); // no neighbors in IFG yet
806 }
807 }
808
809 //------------------------------set_was_low------------------------------------
810 // Set the was-lo-degree bit. Conservative coalescing should not change the
811 // colorability of the graph. If any live range was of low-degree before
812 // coalescing, it should Simplify. This call sets the was-lo-degree bit.
813 // The bit is checked in Simplify.
814 void PhaseChaitin::set_was_low() {
815 #ifdef ASSERT
816 for( uint i = 1; i < _maxlrg; i++ ) {
817 int size = lrgs(i).num_regs();
818 uint old_was_lo = lrgs(i)._was_lo;
819 lrgs(i)._was_lo = 0;
820 if( lrgs(i).lo_degree() ) {
821 lrgs(i)._was_lo = 1; // Trivially of low degree
1087 (reg&1) == 1) ) // or aligned (adjacent reg is available since we already cleared-to-pairs)
1088 return reg;
1089 }
1090 }
1091
1092 uint copy_lrg = Find(lrg._copy_bias);
1093 if( copy_lrg != 0 ) {
1094 // If he has a color,
1095 if( !(*(_ifg->_yanked))[copy_lrg] ) {
1096 OptoReg::Name reg = lrgs(copy_lrg).reg();
1097 // And it is legal for you,
1098 if( reg >= chunk && reg < chunk + RegMask::CHUNK_SIZE &&
1099 lrg.mask().Member(OptoReg::add(reg,-chunk)) &&
1100 (lrg.num_regs()==1 || // either size 1
1101 (reg&1) == 1) ) // or aligned (adjacent reg is available since we already cleared-to-pairs)
1102 return reg;
1103 } else if( chunk == 0 ) {
1104 // Choose a color which is legal for him
1105 RegMask tempmask = lrg.mask();
1106 tempmask.AND(lrgs(copy_lrg).mask());
1107 OptoReg::Name reg;
1108 if( lrg.num_regs() == 1 ) {
1109 reg = tempmask.find_first_elem();
1110 } else {
1111 tempmask.ClearToPairs();
1112 reg = tempmask.find_first_pair();
1113 }
1114 if( OptoReg::is_valid(reg) )
1115 return reg;
1116 }
1117 }
1118
1119 // If no bias info exists, just go with the register selection ordering
1120 if( lrg.num_regs() == 2 ) {
1121 // Find an aligned pair
1122 return OptoReg::add(lrg.mask().find_first_pair(),chunk);
1123 }
1124
1125 // CNC - Fun hack. Alternate 1st and 2nd selection. Enables post-allocate
1126 // copy removal to remove many more copies, by preventing a just-assigned
1127 // register from being repeatedly assigned.
1128 OptoReg::Name reg = lrg.mask().find_first_elem();
1129 if( (++_alternate & 1) && OptoReg::is_valid(reg) ) {
1130 // This 'Remove; find; Insert' idiom is an expensive way to find the
1131 // SECOND element in the mask.
1132 lrg.Remove(reg);
1133 OptoReg::Name reg2 = lrg.mask().find_first_elem();
1134 lrg.Insert(reg);
1135 if( OptoReg::is_reg(reg2))
1136 reg = reg2;
1137 }
1138 return OptoReg::add( reg, chunk );
1139 }
1140
1141 //------------------------------choose_color-----------------------------------
1142 // Choose a color in the current chunk
1143 OptoReg::Name PhaseChaitin::choose_color( LRG &lrg, int chunk ) {
1144 assert( C->in_preserve_stack_slots() == 0 || chunk != 0 || lrg._is_bound || lrg.mask().is_bound1() || !lrg.mask().Member(OptoReg::Name(_matcher._old_SP-1)), "must not allocate stack0 (inside preserve area)");
1145 assert(C->out_preserve_stack_slots() == 0 || chunk != 0 || lrg._is_bound || lrg.mask().is_bound1() || !lrg.mask().Member(OptoReg::Name(_matcher._old_SP+0)), "must not allocate stack0 (inside preserve area)");
1146
1147 if( lrg.num_regs() == 1 || // Common Case
1148 !lrg._fat_proj ) // Aligned+adjacent pairs ok
1149 // Use a heuristic to "bias" the color choice
1150 return bias_color(lrg, chunk);
1151
1152 assert( lrg.num_regs() >= 2, "dead live ranges do not color" );
1153
1154 // Fat-proj case or misaligned double argument.
1155 assert(lrg.compute_mask_size() == lrg.num_regs() ||
1156 lrg.num_regs() == 2,"fat projs exactly color" );
1157 assert( !chunk, "always color in 1st chunk" );
1158 // Return the highest element in the set.
1159 return lrg.mask().find_last_elem();
1160 }
1161
1162 //------------------------------Select-----------------------------------------
1163 // Select colors by re-inserting LRGs back into the IFG. LRGs are re-inserted
1164 // in reverse order of removal. As long as nothing of hi-degree was yanked,
1165 // everything going back is guaranteed a color. Select that color. If some
1166 // hi-degree LRG cannot get a color then we record that we must spill.
1167 uint PhaseChaitin::Select( ) {
1168 uint spill_reg = LRG::SPILL_REG;
1169 _max_reg = OptoReg::Name(0); // Past max register used
1170 while( _simplified ) {
1171 // Pull next LRG from the simplified list - in reverse order of removal
1221 lrg->SUBTRACT(nlrg.mask());
1222 #ifndef PRODUCT
1223 if (trace_spilling() && lrg->mask().Size() != size) {
1224 ttyLocker ttyl;
1225 tty->print("L%d ", lidx);
1226 rm.dump();
1227 tty->print(" intersected L%d ", neighbor);
1228 nlrg.mask().dump();
1229 tty->print(" removed ");
1230 rm.SUBTRACT(lrg->mask());
1231 rm.dump();
1232 tty->print(" leaving ");
1233 lrg->mask().dump();
1234 tty->cr();
1235 }
1236 #endif
1237 }
1238 }
1239 //assert(is_allstack == lrg->mask().is_AllStack(), "nbrs must not change AllStackedness");
1240 // Aligned pairs need aligned masks
1241 if( lrg->num_regs() == 2 && !lrg->_fat_proj )
1242 lrg->ClearToPairs();
1243
1244 // Check if a color is available and if so pick the color
1245 OptoReg::Name reg = choose_color( *lrg, chunk );
1246 #ifdef SPARC
1247 debug_only(lrg->compute_set_mask_size());
1248 assert(lrg->num_regs() != 2 || lrg->is_bound() || is_even(reg-1), "allocate all doubles aligned");
1249 #endif
1250
1251 //---------------
1252 // If we fail to color and the AllStack flag is set, trigger
1253 // a chunk-rollover event
1254 if(!OptoReg::is_valid(OptoReg::add(reg,-chunk)) && is_allstack) {
1255 // Bump register mask up to next stack chunk
1256 chunk += RegMask::CHUNK_SIZE;
1257 lrg->Set_All();
1258
1259 goto retry_next_chunk;
1260 }
1261
1262 //---------------
1263 // Did we get a color?
1264 else if( OptoReg::is_valid(reg)) {
1265 #ifndef PRODUCT
1266 RegMask avail_rm = lrg->mask();
1267 #endif
1268
1269 // Record selected register
1270 lrg->set_reg(reg);
1271
1272 if( reg >= _max_reg ) // Compute max register limit
1273 _max_reg = OptoReg::add(reg,1);
1274 // Fold reg back into normal space
1275 reg = OptoReg::add(reg,-chunk);
1276
1277 // If the live range is not bound, then we actually had some choices
1278 // to make. In this case, the mask has more bits in it than the colors
1279 // chosen. Restrict the mask to just what was picked.
1280 if( lrg->num_regs() == 1 ) { // Size 1 live range
1281 lrg->Clear(); // Clear the mask
1282 lrg->Insert(reg); // Set regmask to match selected reg
1283 lrg->set_mask_size(1);
1284 } else if( !lrg->_fat_proj ) {
1285 // For pairs, also insert the low bit of the pair
1286 assert( lrg->num_regs() == 2, "unbound fatproj???" );
1287 lrg->Clear(); // Clear the mask
1288 lrg->Insert(reg); // Set regmask to match selected reg
1289 lrg->Insert(OptoReg::add(reg,-1));
1290 lrg->set_mask_size(2);
1291 } else { // Else fatproj
1292 // mask must be equal to fatproj bits, by definition
1293 }
1294 #ifndef PRODUCT
1295 if (trace_spilling()) {
1296 ttyLocker ttyl;
1297 tty->print("L%d selected ", lidx);
1298 lrg->mask().dump();
1299 tty->print(" from ");
1300 avail_rm.dump();
1301 tty->cr();
1302 }
1303 #endif
1304 // Note that reg is the highest-numbered register in the newly-bound mask.
1305 } // end color available case
1306
1307 //---------------
1308 // Live range is live and no colors available
1309 else {
1310 assert( lrg->alive(), "" );
1843 sprintf(buf,"%s + #%d",OptoReg::regname(OptoReg::c_frame_pointer),
1844 pc->reg2offset(reg));
1845 return buf+strlen(buf);
1846 }
1847
1848 //------------------------------dump_register----------------------------------
1849 // Dump a register name into a buffer. Be intelligent if we get called
1850 // before allocation is complete.
1851 char *PhaseChaitin::dump_register( const Node *n, char *buf ) const {
1852 if( !this ) { // Not got anything?
1853 sprintf(buf,"N%d",n->_idx); // Then use Node index
1854 } else if( _node_regs ) {
1855 // Post allocation, use direct mappings, no LRG info available
1856 print_reg( get_reg_first(n), this, buf );
1857 } else {
1858 uint lidx = Find_const(n); // Grab LRG number
1859 if( !_ifg ) {
1860 sprintf(buf,"L%d",lidx); // No register binding yet
1861 } else if( !lidx ) { // Special, not allocated value
1862 strcpy(buf,"Special");
1863 } else if( (lrgs(lidx).num_regs() == 1)
1864 ? !lrgs(lidx).mask().is_bound1()
1865 : !lrgs(lidx).mask().is_bound2() ) {
1866 sprintf(buf,"L%d",lidx); // No register binding yet
1867 } else { // Hah! We have a bound machine register
1868 print_reg( lrgs(lidx).reg(), this, buf );
1869 }
1870 }
1871 return buf+strlen(buf);
1872 }
1873
1874 //----------------------dump_for_spill_split_recycle--------------------------
1875 void PhaseChaitin::dump_for_spill_split_recycle() const {
1876 if( WizardMode && (PrintCompilation || PrintOpto) ) {
1877 // Display which live ranges need to be split and the allocator's state
1878 tty->print_cr("Graph-Coloring Iteration %d will split the following live ranges", _trip_cnt);
1879 for( uint bidx = 1; bidx < _maxlrg; bidx++ ) {
1880 if( lrgs(bidx).alive() && lrgs(bidx).reg() >= LRG::SPILL_REG ) {
1881 tty->print("L%d: ", bidx);
1882 lrgs(bidx).dump();
1883 }
1884 }
1885 tty->cr();
1886 dump();
1887 }
1888 }
1889
1890 //------------------------------dump_frame------------------------------------
|
58 if( _degree_valid ) tty->print( "%d ", _eff_degree );
59 else tty->print("? ");
60
61 if( is_multidef() ) {
62 tty->print("MultiDef ");
63 if (_defs != NULL) {
64 tty->print("(");
65 for (int i = 0; i < _defs->length(); i++) {
66 tty->print("N%d ", _defs->at(i)->_idx);
67 }
68 tty->print(") ");
69 }
70 }
71 else if( _def == 0 ) tty->print("Dead ");
72 else tty->print("Def: N%d ",_def->_idx);
73
74 tty->print("Cost:%4.2g Area:%4.2g Score:%4.2g ",_cost,_area, score());
75 // Flags
76 if( _is_oop ) tty->print("Oop ");
77 if( _is_float ) tty->print("Float ");
78 if( _is_vector ) tty->print("Vector ");
79 if( _was_spilled1 ) tty->print("Spilled ");
80 if( _was_spilled2 ) tty->print("Spilled2 ");
81 if( _direct_conflict ) tty->print("Direct_conflict ");
82 if( _fat_proj ) tty->print("Fat ");
83 if( _was_lo ) tty->print("Lo ");
84 if( _has_copy ) tty->print("Copy ");
85 if( _at_risk ) tty->print("Risk ");
86
87 if( _must_spill ) tty->print("Must_spill ");
88 if( _is_bound ) tty->print("Bound ");
89 if( _msize_valid ) {
90 if( _degree_valid && lo_degree() ) tty->print("Trivial ");
91 }
92
93 tty->cr();
94 }
95 #endif
96
97 //------------------------------score------------------------------------------
98 // Compute score from cost and area. Low score is best to spill.
463 _total_framesize += _framesize;
464 if( (int)_framesize > _max_framesize )
465 _max_framesize = _framesize;
466 #endif
467
468 // Convert CISC spills
469 fixup_spills();
470
471 // Log regalloc results
472 CompileLog* log = Compile::current()->log();
473 if (log != NULL) {
474 log->elem("regalloc attempts='%d' success='%d'", _trip_cnt, !C->failing());
475 }
476
477 if (C->failing()) return;
478
479 NOT_PRODUCT( C->verify_graph_edges(); )
480
481 // Move important info out of the live_arena to longer lasting storage.
482 alloc_node_regs(_names.Size());
483 for (uint i=0; i < _names.Size(); i++) {
484 if (_names[i]) { // Live range associated with Node?
485 LRG &lrg = lrgs(_names[i]);
486 if (!lrg.alive()) {
487 _node_regs[i].set_bad();
488 } else if (lrg.num_regs() == 1) {
489 _node_regs[i].set1(lrg.reg());
490 } else { // Must be a register-pair
491 if (!lrg._fat_proj) { // Must be aligned adjacent register pair
492 // Live ranges record the highest register in their mask.
493 // We want the low register for the AD file writer's convenience.
494 _node_regs[i].set2( OptoReg::add(lrg.reg(),(1-lrg.num_regs())) );
495 } else { // Misaligned; extract 2 bits
496 OptoReg::Name hi = lrg.reg(); // Get hi register
497 lrg.Remove(hi); // Yank from mask
498 int lo = lrg.mask().find_first_elem(); // Find lo
499 _node_regs[i].set_pair( hi, lo );
500 }
501 }
502 if( lrg._is_oop ) _node_oops.set(i);
503 } else {
504 _node_regs[i].set_bad();
505 }
506 }
507
508 // Done!
509 _live = NULL;
510 _ifg = NULL;
511 C->set_indexSet_arena(NULL); // ResourceArea is at end of scope
512 }
513
514 //------------------------------de_ssa-----------------------------------------
554 uint input_edge_start =1; // Skip control most nodes
555 if( n->is_Mach() ) input_edge_start = n->as_Mach()->oper_input_base();
556 uint idx = n->is_Copy();
557
558 // Get virtual register number, same as LiveRanGe index
559 uint vreg = n2lidx(n);
560 LRG &lrg = lrgs(vreg);
561 if( vreg ) { // No vreg means un-allocable (e.g. memory)
562
563 // Collect has-copy bit
564 if( idx ) {
565 lrg._has_copy = 1;
566 uint clidx = n2lidx(n->in(idx));
567 LRG ©_src = lrgs(clidx);
568 copy_src._has_copy = 1;
569 }
570
571 // Check for float-vs-int live range (used in register-pressure
572 // calculations)
573 const Type *n_type = n->bottom_type();
574 if (n_type->is_floatingpoint())
575 lrg._is_float = 1;
576
577 // Check for twice prior spilling. Once prior spilling might have
578 // spilled 'soft', 2nd prior spill should have spilled 'hard' and
579 // further spilling is unlikely to make progress.
580 if( _spilled_once.test(n->_idx) ) {
581 lrg._was_spilled1 = 1;
582 if( _spilled_twice.test(n->_idx) )
583 lrg._was_spilled2 = 1;
584 }
585
586 #ifndef PRODUCT
587 if (trace_spilling() && lrg._def != NULL) {
588 // collect defs for MultiDef printing
589 if (lrg._defs == NULL) {
590 lrg._defs = new (_ifg->_arena) GrowableArray<Node*>(_ifg->_arena, 2, 0, NULL);
591 lrg._defs->append(lrg._def);
592 }
593 lrg._defs->append(n);
594 }
595 #endif
596
597 // Check for a single def LRG; these can spill nicely
598 // via rematerialization. Flag as NULL for no def found
599 // yet, or 'n' for single def or -1 for many defs.
600 lrg._def = lrg._def ? NodeSentinel : n;
601
602 // Limit result register mask to acceptable registers
603 const RegMask &rm = n->out_RegMask();
604 lrg.AND( rm );
605
606 int ireg = n->ideal_reg();
607 assert( !n->bottom_type()->isa_oop_ptr() || ireg == Op_RegP,
608 "oops must be in Op_RegP's" );
609
610 // Check for vector live range (only if vector register is used).
611 // On SPARC vector uses RegD which could be misaligned so it is not
612 // processes as vector in RA.
613 if (RegMask::is_vector(ireg))
614 lrg._is_vector = 1;
615 assert(n_type->isa_vect() == NULL || lrg._is_vector || ireg == Op_RegD,
616 "vector must be in vector registers");
617
618 // Check for bound register masks
619 const RegMask &lrgmask = lrg.mask();
620 if (lrgmask.is_bound(ireg))
621 lrg._is_bound = 1;
622
623 // Check for maximum frequency value
624 if (lrg._maxfreq < b->_freq)
625 lrg._maxfreq = b->_freq;
626
627 // Check for oop-iness, or long/double
628 // Check for multi-kill projection
629 switch( ireg ) {
630 case MachProjNode::fat_proj:
631 // Fat projections have size equal to number of registers killed
632 lrg.set_num_regs(rm.Size());
633 lrg.set_reg_pressure(lrg.num_regs());
634 lrg._fat_proj = 1;
635 lrg._is_bound = 1;
636 break;
637 case Op_RegP:
638 #ifdef _LP64
639 lrg.set_num_regs(2); // Size is 2 stack words
640 #else
641 lrg.set_num_regs(1); // Size is 1 stack word
642 #endif
643 // Register pressure is tracked relative to the maximum values
644 // suggested for that platform, INTPRESSURE and FLOATPRESSURE,
645 // and relative to other types which compete for the same regs.
646 //
685 case Op_RegL: // Check for long or double
686 case Op_RegD:
687 lrg.set_num_regs(2);
688 // Define platform specific register pressure
689 #if defined(SPARC) || defined(ARM)
690 lrg.set_reg_pressure(2);
691 #elif defined(IA32)
692 if( ireg == Op_RegL ) {
693 lrg.set_reg_pressure(2);
694 } else {
695 lrg.set_reg_pressure(1);
696 }
697 #else
698 lrg.set_reg_pressure(1); // normally one value per register
699 #endif
700 // If this def of a double forces a mis-aligned double,
701 // flag as '_fat_proj' - really flag as allowing misalignment
702 // AND changes how we count interferences. A mis-aligned
703 // double can interfere with TWO aligned pairs, or effectively
704 // FOUR registers!
705 if (rm.is_misaligned_pair()) {
706 lrg._fat_proj = 1;
707 lrg._is_bound = 1;
708 }
709 break;
710 case Op_RegF:
711 case Op_RegI:
712 case Op_RegN:
713 case Op_RegFlags:
714 case 0: // not an ideal register
715 lrg.set_num_regs(1);
716 #ifdef SPARC
717 lrg.set_reg_pressure(2);
718 #else
719 lrg.set_reg_pressure(1);
720 #endif
721 break;
722 case Op_VecS:
723 assert(Matcher::vector_size_supported(T_BYTE,4), "sanity");
724 assert(RegMask::num_registers(Op_VecS) == RegMask::SlotsPerVecS, "sanity");
725 lrg.set_num_regs(RegMask::SlotsPerVecS);
726 lrg.set_reg_pressure(1);
727 break;
728 case Op_VecD:
729 assert(Matcher::vector_size_supported(T_FLOAT,RegMask::SlotsPerVecD), "sanity");
730 assert(RegMask::num_registers(Op_VecD) == RegMask::SlotsPerVecD, "sanity");
731 assert(lrgmask.is_aligned_sets(RegMask::SlotsPerVecD), "vector should be aligned");
732 lrg.set_num_regs(RegMask::SlotsPerVecD);
733 lrg.set_reg_pressure(1);
734 break;
735 case Op_VecX:
736 assert(Matcher::vector_size_supported(T_FLOAT,RegMask::SlotsPerVecX), "sanity");
737 assert(RegMask::num_registers(Op_VecX) == RegMask::SlotsPerVecX, "sanity");
738 assert(lrgmask.is_aligned_sets(RegMask::SlotsPerVecX), "vector should be aligned");
739 lrg.set_num_regs(RegMask::SlotsPerVecX);
740 lrg.set_reg_pressure(1);
741 break;
742 case Op_VecY:
743 assert(Matcher::vector_size_supported(T_FLOAT,RegMask::SlotsPerVecY), "sanity");
744 assert(RegMask::num_registers(Op_VecY) == RegMask::SlotsPerVecY, "sanity");
745 assert(lrgmask.is_aligned_sets(RegMask::SlotsPerVecY), "vector should be aligned");
746 lrg.set_num_regs(RegMask::SlotsPerVecY);
747 lrg.set_reg_pressure(1);
748 break;
749 default:
750 ShouldNotReachHere();
751 }
752 }
753
754 // Now do the same for inputs
755 uint cnt = n->req();
756 // Setup for CISC SPILLING
757 uint inp = (uint)AdlcVMDeps::Not_cisc_spillable;
758 if( UseCISCSpill && after_aggressive ) {
759 inp = n->cisc_operand();
760 if( inp != (uint)AdlcVMDeps::Not_cisc_spillable )
761 // Convert operand number to edge index number
762 inp = n->as_Mach()->operand_index(inp);
763 }
764 // Prepare register mask for each input
765 for( uint k = input_edge_start; k < cnt; k++ ) {
766 uint vreg = n2lidx(n->in(k));
767 if( !vreg ) continue;
768
786 // int op = m->ideal_Opcode();
787 // if (n->is_Call() && (op == Op_AddF || op == Op_MulF) ) {
788 // int zzz = 1;
789 // }
790 // }
791
792 // Limit result register mask to acceptable registers.
793 // Do not limit registers from uncommon uses before
794 // AggressiveCoalesce. This effectively pre-virtual-splits
795 // around uncommon uses of common defs.
796 const RegMask &rm = n->in_RegMask(k);
797 if( !after_aggressive &&
798 _cfg._bbs[n->in(k)->_idx]->_freq > 1000*b->_freq ) {
799 // Since we are BEFORE aggressive coalesce, leave the register
800 // mask untrimmed by the call. This encourages more coalescing.
801 // Later, AFTER aggressive, this live range will have to spill
802 // but the spiller handles slow-path calls very nicely.
803 } else {
804 lrg.AND( rm );
805 }
806
807 // Check for bound register masks
808 const RegMask &lrgmask = lrg.mask();
809 int kreg = n->in(k)->ideal_reg();
810 bool is_vect = RegMask::is_vector(kreg);
811 assert(n->in(k)->bottom_type()->isa_vect() == NULL ||
812 is_vect || kreg == Op_RegD,
813 "vector must be in vector registers");
814 if (lrgmask.is_bound(kreg))
815 lrg._is_bound = 1;
816
817 // If this use of a double forces a mis-aligned double,
818 // flag as '_fat_proj' - really flag as allowing misalignment
819 // AND changes how we count interferences. A mis-aligned
820 // double can interfere with TWO aligned pairs, or effectively
821 // FOUR registers!
822 #ifdef ASSERT
823 if (is_vect) {
824 assert(lrgmask.is_aligned_sets(lrg.num_regs()), "vector should be aligned");
825 assert(!lrg._fat_proj, "sanity");
826 assert(RegMask::num_registers(kreg) == lrg.num_regs(), "sanity");
827 }
828 #endif
829 if (!is_vect && lrg.num_regs() == 2 && !lrg._fat_proj && rm.is_misaligned_pair()) {
830 lrg._fat_proj = 1;
831 lrg._is_bound = 1;
832 }
833 // if the LRG is an unaligned pair, we will have to spill
834 // so clear the LRG's register mask if it is not already spilled
835 if (!is_vect && !n->is_SpillCopy() &&
836 (lrg._def == NULL || lrg.is_multidef() || !lrg._def->is_SpillCopy()) &&
837 lrgmask.is_misaligned_pair()) {
838 lrg.Clear();
839 }
840
841 // Check for maximum frequency value
842 if( lrg._maxfreq < b->_freq )
843 lrg._maxfreq = b->_freq;
844
845 } // End for all allocated inputs
846 } // end for all instructions
847 } // end for all blocks
848
849 // Final per-liverange setup
850 for (uint i2=0; i2<_maxlrg; i2++) {
851 LRG &lrg = lrgs(i2);
852 assert(!lrg._is_vector || !lrg._fat_proj, "sanity");
853 if (lrg.num_regs() > 1 && !lrg._fat_proj) {
854 lrg.clear_to_sets();
855 }
856 lrg.compute_set_mask_size();
857 if (lrg.not_free()) { // Handle case where we lose from the start
858 lrg.set_reg(OptoReg::Name(LRG::SPILL_REG));
859 lrg._direct_conflict = 1;
860 }
861 lrg.set_degree(0); // no neighbors in IFG yet
862 }
863 }
864
865 //------------------------------set_was_low------------------------------------
866 // Set the was-lo-degree bit. Conservative coalescing should not change the
867 // colorability of the graph. If any live range was of low-degree before
868 // coalescing, it should Simplify. This call sets the was-lo-degree bit.
869 // The bit is checked in Simplify.
870 void PhaseChaitin::set_was_low() {
871 #ifdef ASSERT
872 for( uint i = 1; i < _maxlrg; i++ ) {
873 int size = lrgs(i).num_regs();
874 uint old_was_lo = lrgs(i)._was_lo;
875 lrgs(i)._was_lo = 0;
876 if( lrgs(i).lo_degree() ) {
877 lrgs(i)._was_lo = 1; // Trivially of low degree
1143 (reg&1) == 1) ) // or aligned (adjacent reg is available since we already cleared-to-pairs)
1144 return reg;
1145 }
1146 }
1147
1148 uint copy_lrg = Find(lrg._copy_bias);
1149 if( copy_lrg != 0 ) {
1150 // If he has a color,
1151 if( !(*(_ifg->_yanked))[copy_lrg] ) {
1152 OptoReg::Name reg = lrgs(copy_lrg).reg();
1153 // And it is legal for you,
1154 if( reg >= chunk && reg < chunk + RegMask::CHUNK_SIZE &&
1155 lrg.mask().Member(OptoReg::add(reg,-chunk)) &&
1156 (lrg.num_regs()==1 || // either size 1
1157 (reg&1) == 1) ) // or aligned (adjacent reg is available since we already cleared-to-pairs)
1158 return reg;
1159 } else if( chunk == 0 ) {
1160 // Choose a color which is legal for him
1161 RegMask tempmask = lrg.mask();
1162 tempmask.AND(lrgs(copy_lrg).mask());
1163 tempmask.clear_to_sets(lrg.num_regs());
1164 OptoReg::Name reg = tempmask.find_first_set(lrg.num_regs());
1165 if (OptoReg::is_valid(reg))
1166 return reg;
1167 }
1168 }
1169
1170 // If no bias info exists, just go with the register selection ordering
1171 if (lrg._is_vector || lrg.num_regs() == 2) {
1172 // Find an aligned set
1173 return OptoReg::add(lrg.mask().find_first_set(lrg.num_regs()),chunk);
1174 }
1175
1176 // CNC - Fun hack. Alternate 1st and 2nd selection. Enables post-allocate
1177 // copy removal to remove many more copies, by preventing a just-assigned
1178 // register from being repeatedly assigned.
1179 OptoReg::Name reg = lrg.mask().find_first_elem();
1180 if( (++_alternate & 1) && OptoReg::is_valid(reg) ) {
1181 // This 'Remove; find; Insert' idiom is an expensive way to find the
1182 // SECOND element in the mask.
1183 lrg.Remove(reg);
1184 OptoReg::Name reg2 = lrg.mask().find_first_elem();
1185 lrg.Insert(reg);
1186 if( OptoReg::is_reg(reg2))
1187 reg = reg2;
1188 }
1189 return OptoReg::add( reg, chunk );
1190 }
1191
1192 //------------------------------choose_color-----------------------------------
1193 // Choose a color in the current chunk
1194 OptoReg::Name PhaseChaitin::choose_color( LRG &lrg, int chunk ) {
1195 assert( C->in_preserve_stack_slots() == 0 || chunk != 0 || lrg._is_bound || lrg.mask().is_bound1() || !lrg.mask().Member(OptoReg::Name(_matcher._old_SP-1)), "must not allocate stack0 (inside preserve area)");
1196 assert(C->out_preserve_stack_slots() == 0 || chunk != 0 || lrg._is_bound || lrg.mask().is_bound1() || !lrg.mask().Member(OptoReg::Name(_matcher._old_SP+0)), "must not allocate stack0 (inside preserve area)");
1197
1198 if( lrg.num_regs() == 1 || // Common Case
1199 !lrg._fat_proj ) // Aligned+adjacent pairs ok
1200 // Use a heuristic to "bias" the color choice
1201 return bias_color(lrg, chunk);
1202
1203 assert(!lrg._is_vector, "should be not vector here" );
1204 assert( lrg.num_regs() >= 2, "dead live ranges do not color" );
1205
1206 // Fat-proj case or misaligned double argument.
1207 assert(lrg.compute_mask_size() == lrg.num_regs() ||
1208 lrg.num_regs() == 2,"fat projs exactly color" );
1209 assert( !chunk, "always color in 1st chunk" );
1210 // Return the highest element in the set.
1211 return lrg.mask().find_last_elem();
1212 }
1213
1214 //------------------------------Select-----------------------------------------
1215 // Select colors by re-inserting LRGs back into the IFG. LRGs are re-inserted
1216 // in reverse order of removal. As long as nothing of hi-degree was yanked,
1217 // everything going back is guaranteed a color. Select that color. If some
1218 // hi-degree LRG cannot get a color then we record that we must spill.
1219 uint PhaseChaitin::Select( ) {
1220 uint spill_reg = LRG::SPILL_REG;
1221 _max_reg = OptoReg::Name(0); // Past max register used
1222 while( _simplified ) {
1223 // Pull next LRG from the simplified list - in reverse order of removal
1273 lrg->SUBTRACT(nlrg.mask());
1274 #ifndef PRODUCT
1275 if (trace_spilling() && lrg->mask().Size() != size) {
1276 ttyLocker ttyl;
1277 tty->print("L%d ", lidx);
1278 rm.dump();
1279 tty->print(" intersected L%d ", neighbor);
1280 nlrg.mask().dump();
1281 tty->print(" removed ");
1282 rm.SUBTRACT(lrg->mask());
1283 rm.dump();
1284 tty->print(" leaving ");
1285 lrg->mask().dump();
1286 tty->cr();
1287 }
1288 #endif
1289 }
1290 }
1291 //assert(is_allstack == lrg->mask().is_AllStack(), "nbrs must not change AllStackedness");
1292 // Aligned pairs need aligned masks
1293 assert(!lrg->_is_vector || !lrg->_fat_proj, "sanity");
1294 if (lrg->num_regs() > 1 && !lrg->_fat_proj) {
1295 lrg->clear_to_sets();
1296 }
1297
1298 // Check if a color is available and if so pick the color
1299 OptoReg::Name reg = choose_color( *lrg, chunk );
1300 #ifdef SPARC
1301 debug_only(lrg->compute_set_mask_size());
1302 assert(lrg->num_regs() < 2 || lrg->is_bound() || is_even(reg-1), "allocate all doubles aligned");
1303 #endif
1304
1305 //---------------
1306 // If we fail to color and the AllStack flag is set, trigger
1307 // a chunk-rollover event
1308 if(!OptoReg::is_valid(OptoReg::add(reg,-chunk)) && is_allstack) {
1309 // Bump register mask up to next stack chunk
1310 chunk += RegMask::CHUNK_SIZE;
1311 lrg->Set_All();
1312
1313 goto retry_next_chunk;
1314 }
1315
1316 //---------------
1317 // Did we get a color?
1318 else if( OptoReg::is_valid(reg)) {
1319 #ifndef PRODUCT
1320 RegMask avail_rm = lrg->mask();
1321 #endif
1322
1323 // Record selected register
1324 lrg->set_reg(reg);
1325
1326 if( reg >= _max_reg ) // Compute max register limit
1327 _max_reg = OptoReg::add(reg,1);
1328 // Fold reg back into normal space
1329 reg = OptoReg::add(reg,-chunk);
1330
1331 // If the live range is not bound, then we actually had some choices
1332 // to make. In this case, the mask has more bits in it than the colors
1333 // chosen. Restrict the mask to just what was picked.
1334 int n_regs = lrg->num_regs();
1335 assert(!lrg->_is_vector || !lrg->_fat_proj, "sanity");
1336 if (n_regs == 1 || !lrg->_fat_proj) {
1337 assert(!lrg->_is_vector || n_regs <= RegMask::SlotsPerVecY, "sanity");
1338 lrg->Clear(); // Clear the mask
1339 lrg->Insert(reg); // Set regmask to match selected reg
1340 // For vectors and pairs, also insert the low bit of the pair
1341 for (int i = 1; i < n_regs; i++)
1342 lrg->Insert(OptoReg::add(reg,-i));
1343 lrg->set_mask_size(n_regs);
1344 } else { // Else fatproj
1345 // mask must be equal to fatproj bits, by definition
1346 }
1347 #ifndef PRODUCT
1348 if (trace_spilling()) {
1349 ttyLocker ttyl;
1350 tty->print("L%d selected ", lidx);
1351 lrg->mask().dump();
1352 tty->print(" from ");
1353 avail_rm.dump();
1354 tty->cr();
1355 }
1356 #endif
1357 // Note that reg is the highest-numbered register in the newly-bound mask.
1358 } // end color available case
1359
1360 //---------------
1361 // Live range is live and no colors available
1362 else {
1363 assert( lrg->alive(), "" );
1896 sprintf(buf,"%s + #%d",OptoReg::regname(OptoReg::c_frame_pointer),
1897 pc->reg2offset(reg));
1898 return buf+strlen(buf);
1899 }
1900
1901 //------------------------------dump_register----------------------------------
1902 // Dump a register name into a buffer. Be intelligent if we get called
1903 // before allocation is complete.
1904 char *PhaseChaitin::dump_register( const Node *n, char *buf ) const {
1905 if( !this ) { // Not got anything?
1906 sprintf(buf,"N%d",n->_idx); // Then use Node index
1907 } else if( _node_regs ) {
1908 // Post allocation, use direct mappings, no LRG info available
1909 print_reg( get_reg_first(n), this, buf );
1910 } else {
1911 uint lidx = Find_const(n); // Grab LRG number
1912 if( !_ifg ) {
1913 sprintf(buf,"L%d",lidx); // No register binding yet
1914 } else if( !lidx ) { // Special, not allocated value
1915 strcpy(buf,"Special");
1916 } else {
1917 if (lrgs(lidx)._is_vector) {
1918 if (lrgs(lidx).mask().is_bound_set(lrgs(lidx).num_regs()))
1919 print_reg( lrgs(lidx).reg(), this, buf ); // a bound machine register
1920 else
1921 sprintf(buf,"L%d",lidx); // No register binding yet
1922 } else if( (lrgs(lidx).num_regs() == 1)
1923 ? lrgs(lidx).mask().is_bound1()
1924 : lrgs(lidx).mask().is_bound_pair() ) {
1925 // Hah! We have a bound machine register
1926 print_reg( lrgs(lidx).reg(), this, buf );
1927 } else {
1928 sprintf(buf,"L%d",lidx); // No register binding yet
1929 }
1930 }
1931 }
1932 return buf+strlen(buf);
1933 }
1934
1935 //----------------------dump_for_spill_split_recycle--------------------------
1936 void PhaseChaitin::dump_for_spill_split_recycle() const {
1937 if( WizardMode && (PrintCompilation || PrintOpto) ) {
1938 // Display which live ranges need to be split and the allocator's state
1939 tty->print_cr("Graph-Coloring Iteration %d will split the following live ranges", _trip_cnt);
1940 for( uint bidx = 1; bidx < _maxlrg; bidx++ ) {
1941 if( lrgs(bidx).alive() && lrgs(bidx).reg() >= LRG::SPILL_REG ) {
1942 tty->print("L%d: ", bidx);
1943 lrgs(bidx).dump();
1944 }
1945 }
1946 tty->cr();
1947 dump();
1948 }
1949 }
1950
1951 //------------------------------dump_frame------------------------------------
|