1 #include "llvm/Target/Sparc.h"
2 #include "SparcInternals.h"
3 #include "llvm/Method.h"
4 #include "llvm/iTerminators.h"
5 #include "llvm/iOther.h"
6 #include "llvm/CodeGen/InstrScheduling.h"
7 #include "llvm/CodeGen/InstrSelection.h"
9 #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
10 #include "llvm/CodeGen/PhyRegAlloc.h"
15 //---------------------------------------------------------------------------
17 //---------------------------------------------------------------------------
19 //---------------------------------------------------------------------------
20 // Finds the return value of a call instruction
21 //---------------------------------------------------------------------------
24 UltraSparcRegInfo::getCallInstRetVal(const MachineInstr *CallMI) const{
26 unsigned OpCode = CallMI->getOpCode();
27 unsigned NumOfImpRefs = CallMI->getNumImplicitRefs();
29 if( OpCode == CALL ) {
31 // The one before the last implicit operand is the return value of
33 if( NumOfImpRefs > 1 )
34 if( CallMI->implicitRefIsDefined(NumOfImpRefs-2) )
35 return CallMI->getImplicitRef(NumOfImpRefs-2);
38 else if( OpCode == JMPLCALL) {
40 // The last implicit operand is the return value of a JMPL in
41 if( NumOfImpRefs > 0 )
42 if( CallMI->implicitRefIsDefined(NumOfImpRefs-1) )
43 return CallMI->getImplicitRef(NumOfImpRefs-1);
46 assert(0 && "OpCode must be CALL/JMPL for a call instr");
52 //---------------------------------------------------------------------------
53 // Finds the return address of a call instruction
54 //---------------------------------------------------------------------------
57 UltraSparcRegInfo::getCallInstRetAddr(const MachineInstr *CallMI)const {
59 unsigned OpCode = CallMI->getOpCode();
63 unsigned NumOfImpRefs = CallMI->getNumImplicitRefs();
65 assert( NumOfImpRefs && "CALL instr must have at least on ImpRef");
66 // The last implicit operand is the return address of a CALL instr
67 return CallMI->getImplicitRef(NumOfImpRefs-1);
70 else if( OpCode == JMPLCALL ) {
72 MachineOperand & MO = ( MachineOperand &) CallMI->getOperand(2);
73 return MO.getVRegValue();
77 assert(0 && "OpCode must be CALL/JMPL for a call instr");
79 assert(0 && "There must be a return addr for a call instr");
86 //---------------------------------------------------------------------------
87 // Finds the # of actual arguments of the call instruction
88 //---------------------------------------------------------------------------
91 UltraSparcRegInfo::getCallInstNumArgs(const MachineInstr *CallMI) const {
93 unsigned OpCode = CallMI->getOpCode();
94 unsigned NumOfImpRefs = CallMI->getNumImplicitRefs();
97 if( OpCode == CALL ) {
99 switch( NumOfImpRefs ) {
101 case 0: assert(0 && "A CALL inst must have at least one ImpRef (RetAddr)");
106 default: // two or more implicit refs
107 if( CallMI->implicitRefIsDefined(NumOfImpRefs-2) )
108 NumArgs = NumOfImpRefs - 2; // i.e., NumOfImpRef-2 is the ret val
110 NumArgs = NumOfImpRefs - 1;
114 else if( OpCode == JMPLCALL ) {
116 // The last implicit operand is the return value of a JMPL instr
117 if( NumOfImpRefs > 0 ) {
118 if( CallMI->implicitRefIsDefined(NumOfImpRefs-1) )
119 NumArgs = NumOfImpRefs - 1; // i.e., NumOfImpRef-1 is the ret val
121 NumArgs = NumOfImpRefs;
124 NumArgs = NumOfImpRefs;
127 assert(0 && "OpCode must be CALL/JMPL for a call instr");
129 assert( (NumArgs != -1) && "Internal error in getCallInstNumArgs" );
130 return (unsigned) NumArgs;
136 //---------------------------------------------------------------------------
137 // Suggests a register for the ret address in the RET machine instruction
138 //---------------------------------------------------------------------------
140 void UltraSparcRegInfo::suggestReg4RetAddr(const MachineInstr * RetMI,
141 LiveRangeInfo& LRI) const {
143 assert( (RetMI->getNumOperands() >= 2)
144 && "JMPL/RETURN must have 3 and 2 operands respectively");
146 MachineOperand & MO = ( MachineOperand &) RetMI->getOperand(0);
148 MO.setRegForValue( getUnifiedRegNum( IntRegClassID, SparcIntRegOrder::i7) );
151 // Instead of setting the color, we can suggest one. In that case,
152 // we have to test later whether it received the suggested color.
153 // In that case, a LR has to be created at the start of method.
154 // It has to be done as follows (remove the setRegVal above):
157 const Value *RetAddrVal = MO.getVRegValue();
159 assert( RetAddrVal && "LR for ret address must be created at start");
161 LiveRange * RetAddrLR = LRI.getLiveRangeForValue( RetAddrVal);
162 RetAddrLR->setSuggestedColor(getUnifiedRegNum( IntRegClassID,
163 SparcIntRegOrdr::i7) );
170 //---------------------------------------------------------------------------
171 // Suggests a register for the ret address in the JMPL/CALL machine instr
172 //---------------------------------------------------------------------------
173 void UltraSparcRegInfo::suggestReg4CallAddr(const MachineInstr * CallMI,
175 vector<RegClass *> RCList) const {
178 const Value *RetAddrVal = getCallInstRetAddr( CallMI );
180 // RetAddrVal cannot be NULL (asserted in getCallInstRetAddr)
181 // create a new LR for the return address and color it
183 LiveRange * RetAddrLR = new LiveRange();
184 RetAddrLR->add( RetAddrVal );
185 unsigned RegClassID = getRegClassIDOfValue( RetAddrVal );
186 RetAddrLR->setRegClass( RCList[RegClassID] );
187 RetAddrLR->setColor(getUnifiedRegNum(IntRegClassID,SparcIntRegOrder::o7));
188 LRI.addLRToMap( RetAddrVal, RetAddrLR);
192 assert( (CallMI->getNumOperands() == 3) && "JMPL must have 3 operands");
194 // directly set color since the LR of ret address (if there were one)
195 // will not extend after the call instr
197 MachineOperand & MO = ( MachineOperand &) CallMI->getOperand(2);
198 MO.setRegForValue( getUnifiedRegNum( IntRegClassID,SparcIntRegOrder::o7) );
207 //---------------------------------------------------------------------------
208 // This method will suggest colors to incoming args to a method.
209 // If the arg is passed on stack due to the lack of regs, NOTHING will be
210 // done - it will be colored (or spilled) as a normal value.
211 //---------------------------------------------------------------------------
213 void UltraSparcRegInfo::suggestRegs4MethodArgs(const Method *const Meth,
214 LiveRangeInfo& LRI) const
217 // get the argument list
218 const Method::ArgumentListType& ArgList = Meth->getArgumentList();
219 // get an iterator to arg list
220 Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
223 for( unsigned argNo=0; ArgIt != ArgList.end() ; ++ArgIt, ++argNo) {
226 LiveRange *const LR = LRI.getLiveRangeForValue((const Value *) *ArgIt);
227 assert( LR && "No live range found for method arg");
229 unsigned RegType = getRegType( LR );
232 // if the arg is in int class - allocate a reg for an int arg
233 if( RegType == IntRegType ) {
235 if( argNo < NumOfIntArgRegs) {
236 LR->setSuggestedColor( SparcIntRegOrder::i0 + argNo );
241 // Do NOTHING as this will be colored as a normal value.
242 if (DEBUG_RA) cerr << " Int Regr not suggested for method arg\n";
246 else if( RegType==FPSingleRegType && (argNo*2+1) < NumOfFloatArgRegs)
247 LR->setSuggestedColor( SparcFloatRegOrder::f0 + (argNo * 2 + 1) );
250 else if( RegType == FPDoubleRegType && (argNo*2) < NumOfFloatArgRegs)
251 LR->setSuggestedColor( SparcFloatRegOrder::f0 + (argNo * 2) );
258 //---------------------------------------------------------------------------
260 //---------------------------------------------------------------------------
262 void UltraSparcRegInfo::colorMethodArgs(const Method *const Meth,
264 AddedInstrns *const FirstAI) const {
266 // get the argument list
267 const Method::ArgumentListType& ArgList = Meth->getArgumentList();
268 // get an iterator to arg list
269 Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
275 for( unsigned argNo=0; ArgIt != ArgList.end() ; ++ArgIt, ++argNo) {
278 LiveRange *const LR = LRI.getLiveRangeForValue((const Value *) *ArgIt);
279 assert( LR && "No live range found for method arg");
282 unsigned RegType = getRegType( LR );
283 unsigned RegClassID = (LR->getRegClass())->getID();
286 // find whether this argument is coming in a register (if not, on stack)
288 bool isArgInReg = false;
289 unsigned UniArgReg = InvalidRegNum; // reg that LR MUST be colored with
291 if( (RegType== IntRegType && argNo < NumOfIntArgRegs)) {
293 UniArgReg = getUnifiedRegNum( RegClassID, SparcIntRegOrder::i0 + argNo );
295 else if(RegType == FPSingleRegType && argNo < NumOfFloatArgRegs) {
297 UniArgReg = getUnifiedRegNum( RegClassID,
298 SparcFloatRegOrder::f0 + argNo*2 + 1 ) ;
300 else if(RegType == FPDoubleRegType && argNo < NumOfFloatArgRegs) {
302 UniArgReg = getUnifiedRegNum(RegClassID, SparcFloatRegOrder::f0+argNo*2);
306 if( LR->hasColor() ) {
308 unsigned UniLRReg = getUnifiedRegNum( RegClassID, LR->getColor() );
310 // if LR received the correct color, nothing to do
311 if( UniLRReg == UniArgReg )
314 // We are here because the LR did not have a suggested
315 // color or did not receive the suggested color but LR got a register.
316 // Now we have to copy %ix reg (or stack pos of arg)
317 // to the register it was colored with.
319 // if the arg is coming in UniArgReg register MUST go into
320 // the UniLRReg register
322 AdMI = cpReg2RegMI( UniArgReg, UniLRReg, RegType );
326 // Now the arg is coming on stack. Since the LR recieved a register,
327 // we just have to load the arg on stack into that register
328 const MachineFrameInfo& frameInfo = target.getFrameInfo();
329 assert(frameInfo.argsOnStackHaveFixedSize());
333 frameInfo.getFirstIncomingArgOffset(MachineCodeForMethod::get(Meth), growUp);
335 growUp? firstArg + argNo * frameInfo.getSizeOfEachArgOnStack()
336 : firstArg - argNo * frameInfo.getSizeOfEachArgOnStack();
338 AdMI = cpMem2RegMI(getFramePointer(), offsetFromFP,
342 FirstAI->InstrnsBefore.push_back( AdMI );
344 } // if LR received a color
348 // Now, the LR did not receive a color. But it has a stack offset for
351 // So, if the arg is coming in UniArgReg register, we can just move
352 // that on to the stack pos of LR
357 MachineInstr *AdIBef =
358 cpReg2MemMI(UniArgReg, getFramePointer(),
359 LR->getSpillOffFromFP(), RegType );
361 FirstAI->InstrnsBefore.push_back( AdMI );
366 // Now the arg is coming on stack. Since the LR did NOT
367 // recieved a register as well, it is allocated a stack position. We
368 // can simply change the stack poistion of the LR. We can do this,
369 // since this method is called before any other method that makes
370 // uses of the stack pos of the LR (e.g., updateMachineInstr)
372 const MachineFrameInfo& frameInfo = target.getFrameInfo();
373 assert(frameInfo.argsOnStackHaveFixedSize());
376 int firstArg = frameInfo.getFirstIncomingArgOffset(MachineCodeForMethod::get(Meth), growUp);
378 growUp? firstArg + argNo * frameInfo.getSizeOfEachArgOnStack()
379 : firstArg - argNo * frameInfo.getSizeOfEachArgOnStack();
381 LR->modifySpillOffFromFP( offsetFromFP );
386 } // for each incoming argument
393 //---------------------------------------------------------------------------
394 // This method is called before graph coloring to suggest colors to the
395 // outgoing call args and the return value of the call.
396 //---------------------------------------------------------------------------
397 void UltraSparcRegInfo::suggestRegs4CallArgs(const MachineInstr *const CallMI,
399 vector<RegClass *> RCList) const {
401 assert ( (UltraSparcInfo->getInstrInfo()).isCall(CallMI->getOpCode()) );
403 suggestReg4CallAddr(CallMI, LRI, RCList);
406 // First color the return value of the call instruction. The return value
407 // will be in %o0 if the value is an integer type, or in %f0 if the
408 // value is a float type.
410 // the return value cannot have a LR in machine instruction since it is
411 // only defined by the call instruction
413 // if type is not void, create a new live range and set its
414 // register class and add to LRI
417 const Value *RetVal = getCallInstRetVal( CallMI );
422 assert( (! LRI.getLiveRangeForValue( RetVal ) ) &&
423 "LR for ret Value of call already definded!");
426 // create a new LR for the return value
428 LiveRange * RetValLR = new LiveRange();
429 RetValLR->add( RetVal );
430 unsigned RegClassID = getRegClassIDOfValue( RetVal );
431 RetValLR->setRegClass( RCList[RegClassID] );
432 LRI.addLRToMap( RetVal, RetValLR);
434 // now suggest a register depending on the register class of ret arg
436 if( RegClassID == IntRegClassID )
437 RetValLR->setSuggestedColor(SparcIntRegOrder::o0);
438 else if (RegClassID == FloatRegClassID )
439 RetValLR->setSuggestedColor(SparcFloatRegOrder::f0 );
440 else assert( 0 && "Unknown reg class for return value of call\n");
445 // Now suggest colors for arguments (operands) of the call instruction.
446 // Colors are suggested only if the arg number is smaller than the
447 // the number of registers allocated for argument passing.
448 // Now, go thru call args - implicit operands of the call MI
450 unsigned NumOfCallArgs = getCallInstNumArgs( CallMI );
452 for(unsigned argNo=0, i=0; i < NumOfCallArgs; ++i, ++argNo ) {
454 const Value *CallArg = CallMI->getImplicitRef(i);
456 // get the LR of call operand (parameter)
457 LiveRange *const LR = LRI.getLiveRangeForValue(CallArg);
459 // not possible to have a null LR since all args (even consts)
460 // must be defined before
463 cerr << " ERROR: In call instr, no LR for arg: " ;
464 printValue(CallArg); cerr << endl;
466 assert(0 && "NO LR for call arg");
470 unsigned RegType = getRegType( LR );
472 // if the arg is in int class - allocate a reg for an int arg
473 if( RegType == IntRegType ) {
475 if( argNo < NumOfIntArgRegs)
476 LR->setSuggestedColor( SparcIntRegOrder::o0 + argNo );
479 // Do NOTHING as this will be colored as a normal value.
480 cerr << " Regr not suggested for int call arg" << endl;
483 else if( RegType == FPSingleRegType && (argNo*2 +1)< NumOfFloatArgRegs)
484 LR->setSuggestedColor( SparcFloatRegOrder::f0 + (argNo * 2 + 1) );
487 else if( RegType == FPDoubleRegType && (argNo*2) < NumOfFloatArgRegs)
488 LR->setSuggestedColor( SparcFloatRegOrder::f0 + (argNo * 2) );
491 } // for all call arguments
496 //---------------------------------------------------------------------------
497 // After graph coloring, we have call this method to see whehter the return
498 // value and the call args received the correct colors. If not, we have
499 // to instert copy instructions.
500 //---------------------------------------------------------------------------
502 void UltraSparcRegInfo::colorCallArgs(const MachineInstr *const CallMI,
504 AddedInstrns *const CallAI,
505 PhyRegAlloc &PRA) const {
507 assert ( (UltraSparcInfo->getInstrInfo()).isCall(CallMI->getOpCode()) );
509 // Reset the optional args area in the stack frame
510 // since that is reused for each call
512 PRA.mcInfo.resetOptionalArgs(target);
514 // First color the return value of the call.
515 // If there is a LR for the return value, it means this
516 // method returns a value
520 const Value *RetVal = getCallInstRetVal( CallMI );
524 LiveRange * RetValLR = LRI.getLiveRangeForValue( RetVal );
527 cerr << "\nNo LR for:";
528 printValue( RetVal );
530 assert( RetValLR && "ERR:No LR for non-void return value");
534 unsigned RegClassID = (RetValLR->getRegClass())->getID();
535 bool recvCorrectColor = false;
537 unsigned CorrectCol; // correct color for ret value
538 if(RegClassID == IntRegClassID)
539 CorrectCol = SparcIntRegOrder::o0;
540 else if(RegClassID == FloatRegClassID)
541 CorrectCol = SparcFloatRegOrder::f0;
543 assert( 0 && "Unknown RegClass");
547 // if the LR received the correct color, NOTHING to do
549 if( RetValLR->hasColor() )
550 if( RetValLR->getColor() == CorrectCol )
551 recvCorrectColor = true;
554 // if we didn't receive the correct color for some reason,
555 // put copy instruction
557 if( !recvCorrectColor ) {
559 unsigned RegType = getRegType( RetValLR );
561 // the reg that LR must be colored with
562 unsigned UniRetReg = getUnifiedRegNum( RegClassID, CorrectCol);
564 if( RetValLR->hasColor() ) {
567 UniRetLRReg=getUnifiedRegNum(RegClassID,RetValLR->getColor());
569 // the return value is coming in UniRetReg but has to go into
572 AdMI = cpReg2RegMI( UniRetReg, UniRetLRReg, RegType );
577 // if the LR did NOT receive a color, we have to move the return
578 // value coming in UniRetReg to the stack pos of spilled LR
580 AdMI = cpReg2MemMI(UniRetReg, getFramePointer(),
581 RetValLR->getSpillOffFromFP(), RegType );
584 CallAI->InstrnsAfter.push_back( AdMI );
586 } // the LR didn't receive the suggested color
588 } // if there a return value
591 // Now color all args of the call instruction
593 vector <MachineInstr *> AddedInstrnsBefore;
595 unsigned NumOfCallArgs = getCallInstNumArgs( CallMI );
597 for(unsigned argNo=0, i=0; i < NumOfCallArgs; ++i, ++argNo ) {
599 const Value *CallArg = CallMI->getImplicitRef(i);
601 // get the LR of call operand (parameter)
602 LiveRange *const LR = LRI.getLiveRangeForValue(CallArg);
604 unsigned RegType = getRegType( CallArg );
605 unsigned RegClassID = getRegClassIDOfValue( CallArg);
607 // find whether this argument is coming in a register (if not, on stack)
609 bool isArgInReg = false;
610 unsigned UniArgReg = InvalidRegNum; // reg that LR must be colored with
612 if( (RegType== IntRegType && argNo < NumOfIntArgRegs)) {
614 UniArgReg = getUnifiedRegNum(RegClassID, SparcIntRegOrder::o0 + argNo );
616 else if(RegType == FPSingleRegType && argNo < NumOfFloatArgRegs) {
618 UniArgReg = getUnifiedRegNum(RegClassID,
619 SparcFloatRegOrder::f0 + (argNo*2 + 1) );
621 else if(RegType == FPDoubleRegType && argNo < NumOfFloatArgRegs) {
623 UniArgReg = getUnifiedRegNum(RegClassID, SparcFloatRegOrder::f0+argNo*2);
627 // not possible to have a null LR since all args (even consts)
628 // must be defined before
631 cerr << " ERROR: In call instr, no LR for arg: " ;
632 printValue(CallArg); cerr << endl;
634 assert(0 && "NO LR for call arg");
639 // if the LR received the suggested color, NOTHING to do
642 if( LR->hasColor() ) {
645 unsigned UniLRReg = getUnifiedRegNum( RegClassID, LR->getColor() );
647 // if LR received the correct color, nothing to do
648 if( UniLRReg == UniArgReg )
651 // We are here because though the LR is allocated a register, it
652 // was not allocated the suggested register. So, we have to copy %ix reg
653 // (or stack pos of arg) to the register it was colored with
655 // the LR is colored with UniLRReg but has to go into UniArgReg
656 // to pass it as an argument
659 AdMI = cpReg2RegMI(UniLRReg, UniArgReg, RegType );
662 // Now, we have to pass the arg on stack. Since LR received a register
663 // we just have to move that register to the stack position where
664 // the argument must be passed
666 int argOffset = PRA.mcInfo.allocateOptionalArg(target, LR->getType());
668 AdMI = cpReg2MemMI(UniLRReg, getFramePointer(), argOffset, RegType );
671 AddedInstrnsBefore.push_back( AdMI ); // Now add the instruction
674 else { // LR is not colored (i.e., spilled)
678 // Now the LR did NOT recieve a register but has a stack poistion.
679 // Since, the outgoing arg goes in a register we just have to insert
680 // a load instruction to load the LR to outgoing register
683 AdMI = cpMem2RegMI(getFramePointer(), LR->getSpillOffFromFP(),
684 UniArgReg, RegType );
686 AddedInstrnsBefore.push_back( AdMI ); // Now add the instruction
690 // Now, we have to pass the arg on stack. Since LR also did NOT
691 // receive a register we have to move an argument in memory to
692 // outgoing parameter on stack.
694 // Optoimize: Optimize when reverse pointers in MahineInstr are
696 // call PRA.getUnusedRegAtMI(....) to get an unused reg. Only if this
697 // fails, then use the following code. Currently, we cannot call the
698 // above method since we cannot find LVSetBefore without the BB
700 int TReg = PRA.getRegNotUsedByThisInst( LR->getRegClass(), CallMI );
702 int TmpOff = PRA.mcInfo.pushTempValue(target,
703 target.findOptimalStorageSize(LR->getType()));
704 // getStackOffsets().getNewTmpPosOffFromFP();
706 int argOffset = PRA.mcInfo.allocateOptionalArg(target, LR->getType());
708 MachineInstr *Ad1, *Ad2, *Ad3, *Ad4;
711 // (1) Save TReg on stack
712 // (2) Load LR value into TReg from stack pos of LR
713 // (3) Store Treg on outgoing Arg pos on stack
714 // (4) Load the old value of TReg from stack to TReg (restore it)
716 Ad1 = cpReg2MemMI(TReg, getFramePointer(), TmpOff, RegType );
717 Ad2 = cpMem2RegMI(getFramePointer(), LR->getSpillOffFromFP(),
719 Ad3 = cpReg2MemMI(TReg, getFramePointer(), argOffset, RegType );
720 Ad4 = cpMem2RegMI(getFramePointer(), TmpOff, TReg, RegType );
722 // We directly add to CallAI->InstrnsBefore instead of adding to
723 // AddedInstrnsBefore since these instructions must not be
726 CallAI->InstrnsBefore.push_back( Ad1 );
727 CallAI->InstrnsBefore.push_back( Ad2 );
728 CallAI->InstrnsBefore.push_back( Ad3 );
729 CallAI->InstrnsBefore.push_back( Ad4 );
731 cerr << "\n Caution: Call arg moved from stack to stack";
736 } // for each parameter in call instruction
739 // if we added any instruction before the call instruction, verify
740 // that they are in the proper order and if not, reorder them
742 if( ! AddedInstrnsBefore.empty() ) {
745 cerr << "\nCalling reorder with instrns: \n";
746 for(unsigned i=0; i < AddedInstrnsBefore.size(); i++)
747 cerr << *(AddedInstrnsBefore[i]);
750 vector <MachineInstr *> TmpVec;
751 OrderAddedInstrns(AddedInstrnsBefore, TmpVec, PRA);
754 cerr << "\nAfter reordering instrns: \n";
755 for(unsigned i=0; i < TmpVec.size(); i++)
756 cerr << *(TmpVec[i]);
759 // copy the results back from TmpVec to InstrnsBefore
760 for(unsigned i=0; i < TmpVec.size(); i++)
761 CallAI->InstrnsBefore.push_back( TmpVec[i] );
765 // Reset optional args area again to be safe
766 PRA.mcInfo.resetOptionalArgs(target);
771 //---------------------------------------------------------------------------
772 // This method is called for an LLVM return instruction to identify which
773 // values will be returned from this method and to suggest colors.
774 //---------------------------------------------------------------------------
775 void UltraSparcRegInfo::suggestReg4RetValue(const MachineInstr *const RetMI,
776 LiveRangeInfo& LRI) const {
778 assert( (UltraSparcInfo->getInstrInfo()).isReturn( RetMI->getOpCode() ) );
780 suggestReg4RetAddr(RetMI, LRI);
782 // if there is an implicit ref, that has to be the ret value
783 if( RetMI->getNumImplicitRefs() > 0 ) {
785 // The first implicit operand is the return value of a return instr
786 const Value *RetVal = RetMI->getImplicitRef(0);
789 LiveRange *const LR = LRI.getLiveRangeForValue( RetVal );
792 cerr << "\nNo LR for:";
793 printValue( RetVal );
795 assert( LR && "No LR for return value of non-void method");
799 unsigned RegClassID = (LR->getRegClass())->getID();
801 if( RegClassID == IntRegClassID )
802 LR->setSuggestedColor(SparcIntRegOrder::i0);
804 else if ( RegClassID == FloatRegClassID )
805 LR->setSuggestedColor(SparcFloatRegOrder::f0);
813 //---------------------------------------------------------------------------
814 // Colors the return value of a method to %i0 or %f0, if possible. If it is
815 // not possilbe to directly color the LR, insert a copy instruction to move
816 // the LR to %i0 or %f0. When the LR is spilled, instead of the copy, we
817 // have to put a load instruction.
818 //---------------------------------------------------------------------------
819 void UltraSparcRegInfo::colorRetValue(const MachineInstr *const RetMI,
821 AddedInstrns *const RetAI) const {
823 assert( (UltraSparcInfo->getInstrInfo()).isReturn( RetMI->getOpCode() ) );
825 // if there is an implicit ref, that has to be the ret value
826 if( RetMI->getNumImplicitRefs() > 0 ) {
828 // The first implicit operand is the return value of a return instr
829 const Value *RetVal = RetMI->getImplicitRef(0);
832 LiveRange *const LR = LRI.getLiveRangeForValue( RetVal );
835 cerr << "\nNo LR for:";
836 printValue( RetVal );
838 // assert( LR && "No LR for return value of non-void method");
842 unsigned RegClassID = getRegClassIDOfValue(RetVal);
843 unsigned RegType = getRegType( RetVal );
846 if(RegClassID == IntRegClassID)
847 CorrectCol = SparcIntRegOrder::i0;
848 else if(RegClassID == FloatRegClassID)
849 CorrectCol = SparcFloatRegOrder::f0;
851 assert( 0 && "Unknown RegClass");
855 // if the LR received the correct color, NOTHING to do
858 if( LR->getColor() == CorrectCol )
861 unsigned UniRetReg = getUnifiedRegNum( RegClassID, CorrectCol );
863 if( LR->hasColor() ) {
865 // We are here because the LR was allocted a regiter
866 // It may be the suggested register or not
868 // copy the LR of retun value to i0 or f0
870 unsigned UniLRReg =getUnifiedRegNum( RegClassID, LR->getColor());
872 // the LR received UniLRReg but must be colored with UniRetReg
873 // to pass as the return value
875 AdMI = cpReg2RegMI( UniLRReg, UniRetReg, RegType);
876 RetAI->InstrnsBefore.push_back( AdMI );
878 else { // if the LR is spilled
880 AdMI = cpMem2RegMI(getFramePointer(), LR->getSpillOffFromFP(),
882 RetAI->InstrnsBefore.push_back( AdMI );
883 cout << "\nCopied the return value from stack";
886 } // if there is a return value
891 //---------------------------------------------------------------------------
892 // Copy from a register to register. Register number must be the unified
894 //---------------------------------------------------------------------------
897 MachineInstr * UltraSparcRegInfo::cpReg2RegMI(const unsigned SrcReg,
898 const unsigned DestReg,
899 const int RegType) const {
901 assert( ((int)SrcReg != InvalidRegNum) && ((int)DestReg != InvalidRegNum) &&
904 MachineInstr * MI = NULL;
911 MI = new MachineInstr(ADD, 3);
912 MI->SetMachineOperand(0, SrcReg, false);
913 MI->SetMachineOperand(1, SparcIntRegOrder::g0, false);
914 MI->SetMachineOperand(2, DestReg, true);
917 case FPSingleRegType:
918 MI = new MachineInstr(FMOVS, 2);
919 MI->SetMachineOperand(0, SrcReg, false);
920 MI->SetMachineOperand(1, DestReg, true);
923 case FPDoubleRegType:
924 MI = new MachineInstr(FMOVD, 2);
925 MI->SetMachineOperand(0, SrcReg, false);
926 MI->SetMachineOperand(1, DestReg, true);
930 assert(0 && "Unknow RegType");
937 //---------------------------------------------------------------------------
938 // Copy from a register to memory (i.e., Store). Register number must
939 // be the unified register number
940 //---------------------------------------------------------------------------
943 MachineInstr * UltraSparcRegInfo::cpReg2MemMI(const unsigned SrcReg,
944 const unsigned DestPtrReg,
946 const int RegType) const {
949 MachineInstr * MI = NULL;
955 MI = new MachineInstr(STX, 3);
956 MI->SetMachineOperand(0, SrcReg, false);
957 MI->SetMachineOperand(1, DestPtrReg, false);
958 MI->SetMachineOperand(2, MachineOperand:: MO_SignExtendedImmed,
959 (int64_t) Offset, false);
962 case FPSingleRegType:
963 MI = new MachineInstr(ST, 3);
964 MI->SetMachineOperand(0, SrcReg, false);
965 MI->SetMachineOperand(1, DestPtrReg, false);
966 MI->SetMachineOperand(2, MachineOperand:: MO_SignExtendedImmed,
967 (int64_t) Offset, false);
970 case FPDoubleRegType:
971 MI = new MachineInstr(STD, 3);
972 MI->SetMachineOperand(0, SrcReg, false);
973 MI->SetMachineOperand(1, DestPtrReg, false);
974 MI->SetMachineOperand(2, MachineOperand:: MO_SignExtendedImmed,
975 (int64_t) Offset, false);
979 assert( 0 && "Cannot directly store %ccr to memory");
982 assert(0 && "Unknow RegType in cpReg2MemMI");
989 //---------------------------------------------------------------------------
990 // Copy from memory to a reg (i.e., Load) Register number must be the unified
992 //---------------------------------------------------------------------------
995 MachineInstr * UltraSparcRegInfo::cpMem2RegMI(const unsigned SrcPtrReg,
997 const unsigned DestReg,
998 const int RegType) const {
1000 MachineInstr * MI = NULL;
1005 case FloatCCRegType:
1006 MI = new MachineInstr(LDX, 3);
1007 MI->SetMachineOperand(0, SrcPtrReg, false);
1008 MI->SetMachineOperand(1, MachineOperand:: MO_SignExtendedImmed,
1009 (int64_t) Offset, false);
1010 MI->SetMachineOperand(2, DestReg, true);
1013 case FPSingleRegType:
1014 MI = new MachineInstr(LD, 3);
1015 MI->SetMachineOperand(0, SrcPtrReg, false);
1016 MI->SetMachineOperand(1, MachineOperand:: MO_SignExtendedImmed,
1017 (int64_t) Offset, false);
1018 MI->SetMachineOperand(2, DestReg, true);
1022 case FPDoubleRegType:
1023 MI = new MachineInstr(LDD, 3);
1024 MI->SetMachineOperand(0, SrcPtrReg, false);
1025 MI->SetMachineOperand(1, MachineOperand:: MO_SignExtendedImmed,
1026 (int64_t) Offset, false);
1027 MI->SetMachineOperand(2, DestReg, true);
1031 assert( 0 && "Cannot directly load into %ccr from memory");
1034 assert(0 && "Unknown RegType in cpMem2RegMI");
1043 // Following method is Not needed now
1045 MachineInstr* UltraSparcRegInfo::cpValue2Value(Value *Src, Value *Dest) const {
1047 MachineInstr * MI = NULL;
1049 MI = new MachineInstr(ADD, 3);
1050 MI->SetMachineOperand(0, MachineOperand:: MO_VirtualRegister, Src, false);
1051 MI->SetMachineOperand(1, SparcIntRegOrder::g0, false);
1052 MI->SetMachineOperand(2, MachineOperand:: MO_VirtualRegister, Dest, true);
1061 //----------------------------------------------------------------------------
1062 // This method inserts caller saving/restoring instructons before/after
1063 // a call machine instruction.
1064 //----------------------------------------------------------------------------
1067 void UltraSparcRegInfo::insertCallerSavingCode(const MachineInstr *MInst,
1068 const BasicBlock *BB,
1069 PhyRegAlloc &PRA) const {
1070 // assert( (getInstrInfo()).isCall( MInst->getOpCode() ) );
1072 // Clear the temp area of the stack
1073 PRA.mcInfo.popAllTempValues(target);
1075 hash_set<unsigned> PushedRegSet;
1077 // Now find the LR of the return value of the call
1078 // The last *implicit operand* is the return value of a call
1079 // Insert it to to he PushedRegSet since we must not save that register
1080 // and restore it after the call.
1081 // We do this because, we look at the LV set *after* the instruction
1082 // to determine, which LRs must be saved across calls. The return value
1083 // of the call is live in this set - but we must not save/restore it.
1086 const Value *RetVal = getCallInstRetVal( MInst );
1090 LiveRange *RetValLR = PRA.LRI.getLiveRangeForValue( RetVal );
1091 assert( RetValLR && "No LR for RetValue of call");
1093 if( RetValLR->hasColor())
1094 PushedRegSet.insert(
1095 getUnifiedRegNum((RetValLR->getRegClass())->getID(),
1096 RetValLR->getColor() ) );
1100 const LiveVarSet *LVSetAft = PRA.LVI->getLiveVarSetAfterMInst(MInst, BB);
1102 LiveVarSet::const_iterator LIt = LVSetAft->begin();
1104 // for each live var in live variable set after machine inst
1105 for( ; LIt != LVSetAft->end(); ++LIt) {
1107 // get the live range corresponding to live var
1108 LiveRange *const LR = PRA.LRI.getLiveRangeForValue(*LIt );
1110 // LR can be null if it is a const since a const
1111 // doesn't have a dominating def - see Assumptions above
1114 if( LR->hasColor() ) {
1116 unsigned RCID = (LR->getRegClass())->getID();
1117 unsigned Color = LR->getColor();
1119 if ( isRegVolatile(RCID, Color) ) {
1121 // if the value is in both LV sets (i.e., live before and after
1122 // the call machine instruction)
1124 unsigned Reg = getUnifiedRegNum(RCID, Color);
1126 if( PushedRegSet.find(Reg) == PushedRegSet.end() ) {
1128 // if we haven't already pushed that register
1130 unsigned RegType = getRegType( LR );
1132 // Now get two instructions - to push on stack and pop from stack
1133 // and add them to InstrnsBefore and InstrnsAfter of the
1136 int StackOff = PRA.mcInfo.pushTempValue(target,
1137 target.findOptimalStorageSize(LR->getType()));
1139 MachineInstr *AdIBefCC, *AdIAftCC, *AdICpCC;
1140 MachineInstr *AdIBef, *AdIAft;
1143 //---- Insert code for pushing the reg on stack ----------
1145 if( RegType == IntCCRegType ) {
1147 // Handle IntCCRegType specially since we cannot directly
1148 // push %ccr on to the stack
1150 const LiveVarSet *LVSetBef =
1151 PRA.LVI->getLiveVarSetBeforeMInst(MInst, BB);
1153 // get a free INTEGER register
1155 PRA.getUsableRegAtMI(LR->getRegClass(), IntRegType, MInst,
1156 LVSetBef, AdIBefCC, AdIAftCC);
1158 // insert the instructions in reverse order since we are
1159 // adding them to the front of InstrnsBefore
1162 (PRA.AddedInstrMap[MInst]->InstrnsBefore).push_front(AdIAftCC);
1164 AdICpCC = cpCCR2IntMI(FreeIntReg);
1165 (PRA.AddedInstrMap[MInst]->InstrnsBefore).push_front(AdICpCC);
1168 (PRA.AddedInstrMap[MInst]->InstrnsBefore).push_front(AdIBefCC);
1171 cerr << "\n!! Inserted caller saving (push) inst for %ccr:";
1172 if(AdIBefCC) cerr << "\t" << *(AdIBefCC);
1173 cerr << "\t" << *AdICpCC;
1174 if(AdIAftCC) cerr << "\t" << *(AdIAftCC);
1178 // for any other register type, just add the push inst
1179 AdIBef = cpReg2MemMI(Reg, getFramePointer(), StackOff, RegType );
1180 ((PRA.AddedInstrMap[MInst])->InstrnsBefore).push_front(AdIBef);
1184 //---- Insert code for popping the reg from the stack ----------
1186 if( RegType == IntCCRegType ) {
1188 // Handle IntCCRegType specially since we cannot directly
1189 // pop %ccr on from the stack
1191 // get a free INT register
1193 PRA.getUsableRegAtMI(LR->getRegClass(), IntRegType, MInst,
1194 LVSetAft, AdIBefCC, AdIAftCC);
1197 (PRA.AddedInstrMap[MInst]->InstrnsAfter).push_back(AdIBefCC);
1199 AdICpCC = cpInt2CCRMI(FreeIntReg);
1200 (PRA.AddedInstrMap[MInst]->InstrnsAfter).push_back(AdICpCC);
1203 (PRA.AddedInstrMap[MInst]->InstrnsAfter).push_back(AdIAftCC);
1207 cerr << "\n!! Inserted caller saving (pop) inst for %ccr:";
1208 if(AdIBefCC) cerr << "\t" << *(AdIBefCC);
1209 cerr << "\t" << *AdICpCC;
1210 if(AdIAftCC) cerr << "\t" << *(AdIAftCC);
1214 // for any other register type, just add the pop inst
1215 AdIAft = cpMem2RegMI(getFramePointer(), StackOff, Reg, RegType );
1216 ((PRA.AddedInstrMap[MInst])->InstrnsAfter).push_back(AdIAft);
1219 PushedRegSet.insert( Reg );
1222 cerr << "\nFor call inst:" << *MInst;
1223 cerr << " -inserted caller saving instrs:\n\t ";
1224 if( RegType == IntCCRegType )
1225 cerr << *AdIBefCC << "\t" << *AdIAftCC ;
1227 cerr << *AdIBef << "\t" << *AdIAft ;
1229 } // if not already pushed
1231 } // if LR has a volatile color
1233 } // if LR has color
1235 } // if there is a LR for Var
1237 } // for each value in the LV set after instruction
1239 // Clear the temp area of the stack
1240 PRA.mcInfo.popAllTempValues(target);
1244 //---------------------------------------------------------------------------
1245 // Copies %ccr into an integer register. IntReg is the UNIFIED register
1247 //---------------------------------------------------------------------------
1249 MachineInstr * UltraSparcRegInfo::cpCCR2IntMI(const unsigned IntReg) const {
1250 MachineInstr * MI = NULL;
1252 MI = new MachineInstr(RDCCR, 2);
1253 MI->SetMachineOperand(0, SparcIntCCRegOrder::ccr, false);
1254 MI->SetMachineOperand(1, IntReg, true);
1259 //---------------------------------------------------------------------------
1260 // Copies an integer register into %ccr. IntReg is the UNIFIED register
1262 //---------------------------------------------------------------------------
1264 MachineInstr * UltraSparcRegInfo::cpInt2CCRMI(const unsigned IntReg) const {
1265 MachineInstr * MI = NULL;
1267 MI = new MachineInstr(WRCCR, 3);
1268 MI->SetMachineOperand(0, IntReg, false);
1269 MI->SetMachineOperand(1, SparcIntRegOrder::g0, false);
1270 MI->SetMachineOperand(2, SparcIntCCRegOrder::ccr, true);
1278 //---------------------------------------------------------------------------
1279 // Print the register assigned to a LR
1280 //---------------------------------------------------------------------------
1282 void UltraSparcRegInfo::printReg(const LiveRange *const LR) {
1284 unsigned RegClassID = (LR->getRegClass())->getID();
1286 cerr << " *Node " << (LR->getUserIGNode())->getIndex();
1288 if( ! LR->hasColor() ) {
1289 cerr << " - could not find a color" << endl;
1293 // if a color is found
1295 cerr << " colored with color "<< LR->getColor();
1297 if( RegClassID == IntRegClassID ) {
1299 cerr<< " [" << SparcIntRegOrder::getRegName(LR->getColor()) ;
1300 cerr << "]" << endl;
1302 else if ( RegClassID == FloatRegClassID) {
1303 cerr << "[" << SparcFloatRegOrder::getRegName(LR->getColor());
1304 if( LR->getTypeID() == Type::DoubleTyID )
1305 cerr << "+" << SparcFloatRegOrder::getRegName(LR->getColor()+1);
1306 cerr << "]" << endl;
1310 //---------------------------------------------------------------------------
1311 // This method examines instructions inserted by RegAlloc code before a
1312 // machine instruction to detect invalid orders that destroy values before
1313 // they are used. If it detects such conditions, it reorders the instructions.
1315 // The unordered instructions come in the UnordVec. These instructions are
1316 // instructions inserted by RegAlloc. All such instruction MUST have
1317 // their USES BEFORE THE DEFS after reordering.
1319 // The UnordVec & OrdVec must be DISTINCT. The OrdVec must be empty when
1320 // this method is called.
1322 // This method uses two vectors for efficiency in accessing
1324 // Since instructions are inserted in RegAlloc, this assumes that the
1325 // first operand is the source reg and the last operand is the dest reg.
1327 // All the uses are before THE def to a register
1330 //---------------------------------------------------------------------------
1331 void UltraSparcRegInfo::OrderAddedInstrns( vector<MachineInstr *> &UnordVec,
1332 vector<MachineInstr *> &OrdVec,
1333 PhyRegAlloc &PRA) const{
1336 Problem: We can have instructions inserted by RegAlloc like
1338 2. add %oy %g0 %oz, where z!=x or z==x
1340 This is wrong since %oy used by 2 is overwritten by 1
1343 We re-order the instructions so that the uses are before the defs
1348 for each instruction 'DefInst' in the UnOrdVec
1349 for each instruction 'UseInst' that follows the DefInst
1350 if the reg defined by DefInst is used by UseInst
1351 mark DefInst as not movable in this iteration
1352 If DefInst is not marked as not-movable, move DefInst to OrdVec
1353 while all instructions in DefInst are moved to OrdVec
1355 For moving, we call the move2OrdVec(). It checks whether there is a def
1356 in it for the uses in the instruction to be added to OrdVec. If there
1357 are no preceding defs, it just appends the instruction. If there is a
1358 preceding def, it puts two instructions to save the reg on stack before
1359 the load and puts a restore at use.
1365 bool DebugPrint = false;
1369 CouldMoveAll = true;
1371 vector<MachineInstr *>::iterator DefIt = UnordVec.begin();
1373 for( ; DefIt != UnordVec.end(); ++DefIt ) {
1375 // for each instruction in the UnordVec do ...
1377 MachineInstr *DefInst = *DefIt;
1379 if( DefInst == NULL) continue;
1381 //cerr << "\nInst in UnordVec = " << *DefInst;
1383 // last operand is the def (unless for a store which has no def reg)
1384 MachineOperand& DefOp = DefInst->getOperand(DefInst->getNumOperands()-1);
1386 if( DefOp.opIsDef() &&
1387 DefOp.getOperandType() == MachineOperand::MO_MachineRegister) {
1389 // If the operand in DefInst is a def ...
1391 bool DefEqUse = false;
1393 vector<MachineInstr *>::iterator UseIt = DefIt;
1396 for( ; UseIt != UnordVec.end(); ++UseIt ) {
1398 MachineInstr *UseInst = *UseIt;
1399 if( UseInst == NULL) continue;
1401 // for each inst (UseInst) that is below the DefInst do ...
1404 MachineOperand& UseOp = UseInst->getOperand(0);
1406 if( ! UseOp.opIsDef() &&
1407 UseOp.getOperandType() == MachineOperand::MO_MachineRegister) {
1409 // if use is a register ...
1411 if( DefOp.getMachineRegNum() == UseOp.getMachineRegNum() ) {
1413 // if Def and this use are the same, it means that this use
1414 // is destroyed by a def before it is used
1416 // cerr << "\nCouldn't move " << *DefInst;
1419 CouldMoveAll = false;
1422 } // if two registers are equal
1424 } // if use is a register
1426 }// for all use instructions
1430 // after examining all the instructions that follow the DefInst
1431 // if there are no dependencies, we can move it to the OrdVec
1433 // cerr << "Moved to Ord: " << *DefInst;
1435 moveInst2OrdVec(OrdVec, DefInst, PRA);
1437 //OrdVec.push_back(DefInst);
1439 // mark the pos of DefInst with NULL to indicate that it is
1444 } // if Def is a machine register
1446 } // for all instructions in the UnordVec
1449 } while( !CouldMoveAll);
1453 cerr << "\nAdded instructions were reordered to:\n";
1454 for(unsigned int i=0; i < OrdVec.size(); i++)
1455 cerr << *(OrdVec[i]);
1467 void UltraSparcRegInfo::moveInst2OrdVec(vector<MachineInstr *> &OrdVec,
1468 MachineInstr *UnordInst,
1469 PhyRegAlloc &PRA ) const {
1471 MachineOperand& UseOp = UnordInst->getOperand(0);
1473 if( ! UseOp.opIsDef() &&
1474 UseOp.getOperandType() == MachineOperand::MO_MachineRegister) {
1476 // for the use of UnordInst, see whether there is a defining instr
1477 // before in the OrdVec
1478 bool DefEqUse = false;
1480 vector<MachineInstr *>::iterator OrdIt = OrdVec.begin();
1482 for( ; OrdIt != OrdVec.end(); ++OrdIt ) {
1484 MachineInstr *OrdInst = *OrdIt ;
1486 MachineOperand& DefOp =
1487 OrdInst->getOperand(OrdInst->getNumOperands()-1);
1489 if( DefOp.opIsDef() &&
1490 DefOp.getOperandType() == MachineOperand::MO_MachineRegister) {
1492 //cerr << "\nDefining Ord Inst: " << *OrdInst;
1494 if( DefOp.getMachineRegNum() == UseOp.getMachineRegNum() ) {
1496 // we are here because there is a preceding def in the OrdVec
1497 // for the use in this intr we are going to insert. This
1498 // happened because the original code was like:
1499 // 1. add %ox %g0 %oy
1500 // 2. add %oy %g0 %ox
1501 // In Round1, we added 2 to OrdVec but 1 remained in UnordVec
1502 // Now we are processing %ox of 1.
1505 const int UReg = DefOp.getMachineRegNum();
1506 const int RegType = getRegType(UReg);
1507 MachineInstr *AdIBef, *AdIAft;
1509 // TODO: Change 8 below
1510 const int StackOff = PRA.mcInfo.pushTempValue(target, 8);
1512 // Save the UReg (%ox) on stack before it's destroyed
1513 AdIBef=cpReg2MemMI(UReg, getFramePointer(), StackOff, RegType);
1514 OrdIt = OrdVec.insert( OrdIt, AdIBef);
1515 OrdIt++; // points to current instr we processed
1517 // Load directly into DReg (%oy)
1518 MachineOperand& DOp=
1519 (UnordInst->getOperand(UnordInst->getNumOperands()-1));
1520 assert(DOp.opIsDef() && "Last operand is not the def");
1521 const int DReg = DOp.getMachineRegNum();
1523 AdIAft=cpMem2RegMI(getFramePointer(), StackOff, DReg, RegType);
1524 OrdVec.push_back(AdIAft);
1526 cerr << "\nFixed CIRCULAR references by reordering";
1529 cerr << "\nBefore CIRCULAR Reordering:\n";
1533 cerr << "\nAfter CIRCULAR Reordering - All Inst so far:\n";
1534 for(unsigned i=0; i < OrdVec.size(); i++)
1535 cerr << *(OrdVec[i]);
1538 // Do not copy the UseInst to OrdVec
1542 }// if two registers are equal
1544 } // if Def is a register
1546 } // for each instr in OrdVec
1550 // We didn't find a def in the OrdVec, so just append this inst
1551 OrdVec.push_back( UnordInst );
1552 //cerr << "Reordered Inst (Moved Dn): " << *UnordInst;
1555 }// if the operand in UnordInst is a use