lib/Target/SparcV9/SparcV9RegInfo.cpp

   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"
   8 #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
   9 #include "llvm/CodeGen/PhyRegAlloc.h"
  10 #include "llvm/DerivedTypes.h"
  11 #include <iostream>
  12 using std::cerr;
  13
  14 //---------------------------------------------------------------------------
  15 // Purpose:
  16 // This file contains implementation of Sparc specific helper methods
  17 // used for register allocation.
  18 //---------------------------------------------------------------------------
  19
  20
  21 //---------------------------------------------------------------------------
  22 // Finds the return value of a sparc specific call instruction
  23 //---------------------------------------------------------------------------
  24 const Value *
  25 UltraSparcRegInfo::getCallInstRetVal(const MachineInstr *CallMI) const {
  26   unsigned OpCode = CallMI->getOpCode();
  27   unsigned NumOfImpRefs = CallMI->getNumImplicitRefs();
  28
  29   if (OpCode == CALL) {
  30
  31     // The one before the last implicit operand is the return value of
  32     // a CALL instr
  33     //
  34     if( NumOfImpRefs > 1 )
  35       if(  CallMI->implicitRefIsDefined(NumOfImpRefs-2) )
  36         return  CallMI->getImplicitRef(NumOfImpRefs-2);
  37
  38   } else if (OpCode == JMPLCALL) {
  39
  40     // The last implicit operand is the return value of a JMPL
  41     //
  42     if(NumOfImpRefs > 0)
  43       if (CallMI->implicitRefIsDefined(NumOfImpRefs-1))
  44         return CallMI->getImplicitRef(NumOfImpRefs-1);
  45   }
  46   else
  47     assert(0 && "OpCode must be CALL/JMPL for a call instr");
  48
  49   return NULL;
  50 }
  51
  52
  53
  54 //---------------------------------------------------------------------------
  55 // Finds the return address of a call sparc specific call instruction
  56 //---------------------------------------------------------------------------
  57 const Value *
  58 UltraSparcRegInfo::getCallInstRetAddr(const MachineInstr *CallMI)const {
  59
  60   unsigned OpCode = CallMI->getOpCode();
  61
  62   if( OpCode == CALL) {
  63
  64     unsigned NumOfImpRefs =  CallMI->getNumImplicitRefs();
  65
  66     assert( NumOfImpRefs && "CALL instr must have at least on ImpRef");
  67
  68     // The last implicit operand is the return address of a CALL instr
  69     //
  70     return  CallMI->getImplicitRef(NumOfImpRefs-1);
  71
  72   }
  73   else if( OpCode == JMPLCALL ) {
  74
  75     MachineOperand & MO  = ( MachineOperand &) CallMI->getOperand(2);
  76     return MO.getVRegValue();
  77
  78   }
  79   else
  80     assert(0 && "OpCode must be CALL/JMPL for a call instr");
  81
  82   assert(0  && "There must be a return addr for a call instr");
  83
  84   return NULL;
  85 }
  86
  87
  88
  89 //---------------------------------------------------------------------------
  90 // Finds the # of actual arguments of the call instruction
  91 //---------------------------------------------------------------------------
  92 const unsigned
  93 UltraSparcRegInfo::getCallInstNumArgs(const MachineInstr *CallMI) const {
  94
  95   unsigned OpCode = CallMI->getOpCode();
  96   unsigned NumOfImpRefs =  CallMI->getNumImplicitRefs();
  97   int NumArgs = -1;
  98
  99   if( OpCode == CALL ) {
 100
 101     switch( NumOfImpRefs ) {
 102
 103     case 0: assert(0 && "A CALL inst must have at least one ImpRef (RetAddr)");
 104
 105     case 1: NumArgs = 0;
 106             break;
 107
 108     default:  // two or more implicit refs
 109       if(  CallMI->implicitRefIsDefined(NumOfImpRefs-2) )
 110         NumArgs = NumOfImpRefs - 2;    // i.e., NumOfImpRef-2 is the ret val
 111       else
 112         NumArgs = NumOfImpRefs - 1;
 113     }
 114
 115   }
 116   else if( OpCode == JMPLCALL ) {
 117
 118     // The last implicit operand is the return value of a JMPL instr
 119     if( NumOfImpRefs > 0 ) {
 120       if(  CallMI->implicitRefIsDefined(NumOfImpRefs-1) )
 121         NumArgs = NumOfImpRefs - 1;    // i.e., NumOfImpRef-1 is the ret val
 122       else
 123         NumArgs = NumOfImpRefs;
 124     }
 125     else
 126       NumArgs = NumOfImpRefs;
 127   }
 128   else
 129     assert(0 && "OpCode must be CALL/JMPL for a call instr");
 130
 131   assert( (NumArgs != -1)  && "Internal error in getCallInstNumArgs" );
 132   return (unsigned) NumArgs;
 133 }
 134
 135
 136
 137 //---------------------------------------------------------------------------
 138 // Finds whether a call is an indirect call
 139 //---------------------------------------------------------------------------
 140 bool UltraSparcRegInfo::isVarArgCall(const MachineInstr *CallMI) const {
 141
 142   assert ( (UltraSparcInfo->getInstrInfo()).isCall(CallMI->getOpCode()) );
 143
 144   const MachineOperand & calleeOp = CallMI->getOperand(0);
 145   Value *calleeVal =  calleeOp.getVRegValue();
 146
 147   PointerType *PT =  cast<PointerType> (calleeVal->getType());
 148   MethodType  *MT = cast<MethodType>(PT->getElementType());
 149
 150   return MT->isVarArg();
 151 }
 152
 153
 154
 155
 156 //---------------------------------------------------------------------------
 157 // Suggests a register for the ret address in the RET machine instruction.
 158 // We always suggest %i7 by convention.
 159 //---------------------------------------------------------------------------
 160 void UltraSparcRegInfo::suggestReg4RetAddr(const MachineInstr * RetMI,
 161                                            LiveRangeInfo& LRI) const {
 162
 163   assert( (RetMI->getNumOperands() >= 2)
 164           && "JMPL/RETURN must have 3 and 2 operands respectively");
 165
 166   MachineOperand & MO  = ( MachineOperand &) RetMI->getOperand(0);
 167
 168   // return address is always mapped to i7
 169   //
 170   MO.setRegForValue( getUnifiedRegNum( IntRegClassID, SparcIntRegOrder::i7) );
 171
 172   // Possible Optimization:
 173   // Instead of setting the color, we can suggest one. In that case,
 174   // we have to test later whether it received the suggested color.
 175   // In that case, a LR has to be created at the start of method.
 176   // It has to be done as follows (remove the setRegVal above):
 177
 178   // const Value *RetAddrVal = MO.getVRegValue();
 179   // assert( RetAddrVal && "LR for ret address must be created at start");
 180   // LiveRange * RetAddrLR = LRI.getLiveRangeForValue( RetAddrVal);
 181   // RetAddrLR->setSuggestedColor(getUnifiedRegNum( IntRegClassID,
 182   // SparcIntRegOrdr::i7) );
 183 }
 184
 185
 186 //---------------------------------------------------------------------------
 187 // Suggests a register for the ret address in the JMPL/CALL machine instr.
 188 // Sparc ABI dictates that %o7 be used for this purpose.
 189 //---------------------------------------------------------------------------
 190 void UltraSparcRegInfo::suggestReg4CallAddr(const MachineInstr * CallMI,
 191                                             LiveRangeInfo& LRI,
 192                                          std::vector<RegClass *> RCList) const {
 193
 194
 195   const Value *RetAddrVal = getCallInstRetAddr( CallMI );
 196
 197   // RetAddrVal cannot be NULL (asserted in  getCallInstRetAddr)
 198   // create a new LR for the return address and color it
 199
 200   LiveRange * RetAddrLR = new LiveRange();
 201   RetAddrLR->add( RetAddrVal );
 202   unsigned RegClassID = getRegClassIDOfValue( RetAddrVal );
 203   RetAddrLR->setRegClass( RCList[RegClassID] );
 204   RetAddrLR->setColor(getUnifiedRegNum(IntRegClassID,SparcIntRegOrder::o7));
 205   LRI.addLRToMap( RetAddrVal, RetAddrLR);
 206
 207 }
 208
 209
 210
 211
 212 //---------------------------------------------------------------------------
 213 //  This method will suggest colors to incoming args to a method.
 214 //  According to the Sparc ABI, the first 6 incoming args are in
 215 //  %i0 - %i5 (if they are integer) OR in %f0 - %f31 (if they are float).
 216 //  If the arg is passed on stack due to the lack of regs, NOTHING will be
 217 //  done - it will be colored (or spilled) as a normal live range.
 218 //---------------------------------------------------------------------------
 219 void UltraSparcRegInfo::suggestRegs4MethodArgs(const Method *const Meth,
 220                                                LiveRangeInfo& LRI) const
 221 {
 222
 223                                                  // get the argument list
 224   const Method::ArgumentListType& ArgList = Meth->getArgumentList();
 225                                                  // get an iterator to arg list
 226   Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
 227
 228   // for each argument
 229   for( unsigned argNo=0; ArgIt != ArgList.end() ; ++ArgIt, ++argNo) {
 230
 231     // get the LR of arg
 232     LiveRange *const LR = LRI.getLiveRangeForValue((const Value *) *ArgIt);
 233     assert( LR && "No live range found for method arg");
 234
 235     unsigned RegType = getRegType( LR );
 236
 237
 238     // if the arg is in int class - allocate a reg for an int arg
 239     //
 240     if( RegType == IntRegType ) {
 241
 242       if( argNo < NumOfIntArgRegs) {
 243         LR->setSuggestedColor( SparcIntRegOrder::i0 + argNo );
 244       }
 245       else {
 246         // Do NOTHING as this will be colored as a normal value.
 247         if (DEBUG_RA) cerr << " Int Regr not suggested for method arg\n";
 248       }
 249
 250     }
 251     else if( RegType==FPSingleRegType && (argNo*2+1) < NumOfFloatArgRegs)
 252       LR->setSuggestedColor( SparcFloatRegOrder::f0 + (argNo * 2 + 1) );
 253
 254
 255     else if( RegType == FPDoubleRegType && (argNo*2) < NumOfFloatArgRegs)
 256       LR->setSuggestedColor( SparcFloatRegOrder::f0 + (argNo * 2) );
 257
 258   }
 259 }
 260
 261
 262
 263 //---------------------------------------------------------------------------
 264 // This method is called after graph coloring to move incoming args to
 265 // the correct hardware registers if they did not receive the correct
 266 // (suggested) color through graph coloring.
 267 //---------------------------------------------------------------------------
 268 void UltraSparcRegInfo::colorMethodArgs(const Method *const Meth,
 269                                         LiveRangeInfo& LRI,
 270                                         AddedInstrns *const FirstAI) const {
 271
 272                                                  // get the argument list
 273   const Method::ArgumentListType& ArgList = Meth->getArgumentList();
 274                                                  // get an iterator to arg list
 275   Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
 276
 277   MachineInstr *AdMI;
 278
 279
 280   // for each argument
 281   for( unsigned argNo=0; ArgIt != ArgList.end() ; ++ArgIt, ++argNo) {
 282
 283     // get the LR of arg
 284     LiveRange *const LR = LRI.getLiveRangeForValue((const Value *) *ArgIt);
 285     assert( LR && "No live range found for method arg");
 286
 287
 288     unsigned RegType = getRegType( LR );
 289     unsigned RegClassID = (LR->getRegClass())->getID();
 290
 291     // Find whether this argument is coming in a register (if not, on stack)
 292     // Also find the correct register that the argument must go (UniArgReg)
 293     //
 294     bool isArgInReg = false;
 295     unsigned UniArgReg = InvalidRegNum; // reg that LR MUST be colored with
 296
 297     if( (RegType== IntRegType && argNo <  NumOfIntArgRegs)) {
 298       isArgInReg = true;
 299       UniArgReg = getUnifiedRegNum( RegClassID, SparcIntRegOrder::i0 + argNo );
 300     }
 301     else if(RegType == FPSingleRegType && argNo < NumOfFloatArgRegs)  {
 302       isArgInReg = true;
 303       UniArgReg = getUnifiedRegNum( RegClassID,
 304                                     SparcFloatRegOrder::f0 + argNo*2 + 1 ) ;
 305     }
 306     else if(RegType == FPDoubleRegType && argNo < NumOfFloatArgRegs)  {
 307       isArgInReg = true;
 308       UniArgReg = getUnifiedRegNum(RegClassID, SparcFloatRegOrder::f0+argNo*2);
 309     }
 310
 311
 312     if( LR->hasColor() ) {              // if this arg received a register
 313
 314       unsigned UniLRReg = getUnifiedRegNum(  RegClassID, LR->getColor() );
 315
 316       // if LR received the correct color, nothing to do
 317       //
 318       if( UniLRReg == UniArgReg )
 319         continue;
 320
 321       // We are here because the LR did not receive the suggested
 322       // but LR received another register.
 323       // Now we have to copy the %i reg (or stack pos of arg)
 324       // to the register the LR was colored with.
 325
 326       // if the arg is coming in UniArgReg register, it MUST go into
 327       // the UniLRReg register
 328       //
 329       if( isArgInReg )
 330         AdMI = cpReg2RegMI( UniArgReg, UniLRReg, RegType );
 331
 332       else {
 333
 334         // Now the arg is coming on stack. Since the LR recieved a register,
 335         // we just have to load the arg on stack into that register
 336         //
 337         const MachineFrameInfo& frameInfo = target.getFrameInfo();
 338         assert(frameInfo.argsOnStackHaveFixedSize());
 339
 340         bool growUp;                    // find the offset of arg in stack frame
 341         int firstArg =
 342           frameInfo.getFirstIncomingArgOffset(MachineCodeForMethod::get(Meth),
 343                                               growUp);
 344         int offsetFromFP =
 345           growUp? firstArg + argNo * frameInfo.getSizeOfEachArgOnStack()
 346                 : firstArg - argNo * frameInfo.getSizeOfEachArgOnStack();
 347
 348         AdMI = cpMem2RegMI(getFramePointer(), offsetFromFP,
 349                            UniLRReg, RegType );
 350       }
 351
 352       FirstAI->InstrnsBefore.push_back( AdMI );
 353
 354     } // if LR received a color
 355
 356     else {
 357
 358       // Now, the LR did not receive a color. But it has a stack offset for
 359       // spilling.
 360       // So, if the arg is coming in UniArgReg register,  we can just move
 361       // that on to the stack pos of LR
 362
 363       if( isArgInReg ) {
 364         cpReg2MemMI(UniArgReg, getFramePointer(),
 365                     LR->getSpillOffFromFP(), RegType );
 366
 367         FirstAI->InstrnsBefore.push_back( AdMI );
 368       }
 369
 370       else {
 371
 372         // Now the arg is coming on stack. Since the LR did NOT
 373         // recieved a register as well, it is allocated a stack position. We
 374         // can simply change the stack poistion of the LR. We can do this,
 375         // since this method is called before any other method that makes
 376         // uses of the stack pos of the LR (e.g., updateMachineInstr)
 377
 378         const MachineFrameInfo& frameInfo = target.getFrameInfo();
 379         assert(frameInfo.argsOnStackHaveFixedSize());
 380
 381         bool growUp;
 382         int firstArg = frameInfo.getFirstIncomingArgOffset(MachineCodeForMethod::get(Meth), growUp);
 383         int offsetFromFP =
 384           growUp? firstArg + argNo * frameInfo.getSizeOfEachArgOnStack()
 385                 : firstArg - argNo * frameInfo.getSizeOfEachArgOnStack();
 386
 387         LR->modifySpillOffFromFP( offsetFromFP );
 388       }
 389
 390     }
 391
 392   }  // for each incoming argument
 393
 394 }
 395
 396
 397
 398
 399 //---------------------------------------------------------------------------
 400 // This method is called before graph coloring to suggest colors to the
 401 // outgoing call args and the return value of the call.
 402 //---------------------------------------------------------------------------
 403 void UltraSparcRegInfo::suggestRegs4CallArgs(const MachineInstr *const CallMI,
 404                                              LiveRangeInfo& LRI,
 405                                          std::vector<RegClass *> RCList) const {
 406
 407   assert ( (UltraSparcInfo->getInstrInfo()).isCall(CallMI->getOpCode()) );
 408
 409   suggestReg4CallAddr(CallMI, LRI, RCList);
 410
 411
 412   // First color the return value of the call instruction. The return value
 413   // will be in %o0 if the value is an integer type, or in %f0 if the
 414   // value is a float type.
 415
 416   // the return value cannot have a LR in machine instruction since it is
 417   // only defined by the call instruction
 418
 419   // if type is not void,  create a new live range and set its
 420   // register class and add to LRI
 421
 422
 423   const Value *RetVal = getCallInstRetVal( CallMI );
 424
 425
 426   if( RetVal ) {
 427
 428     assert( (! LRI.getLiveRangeForValue( RetVal ) ) &&
 429             "LR for ret Value of call already definded!");
 430
 431
 432       // create a new LR for the return value
 433
 434     LiveRange * RetValLR = new LiveRange();
 435     RetValLR->add( RetVal );
 436     unsigned RegClassID = getRegClassIDOfValue( RetVal );
 437     RetValLR->setRegClass( RCList[RegClassID] );
 438     LRI.addLRToMap( RetVal, RetValLR);
 439
 440     // now suggest a register depending on the register class of ret arg
 441
 442     if( RegClassID == IntRegClassID )
 443       RetValLR->setSuggestedColor(SparcIntRegOrder::o0);
 444     else if (RegClassID == FloatRegClassID )
 445       RetValLR->setSuggestedColor(SparcFloatRegOrder::f0 );
 446     else assert( 0 && "Unknown reg class for return value of call\n");
 447
 448   }
 449
 450
 451   // Now suggest colors for arguments (operands) of the call instruction.
 452   // Colors are suggested only if the arg number is smaller than the
 453   // the number of registers allocated for argument passing.
 454   // Now, go thru call args - implicit operands of the call MI
 455
 456   unsigned NumOfCallArgs =  getCallInstNumArgs( CallMI );
 457
 458   for(unsigned argNo=0, i=0; i < NumOfCallArgs; ++i, ++argNo ) {
 459
 460     const Value *CallArg = CallMI->getImplicitRef(i);
 461
 462     // get the LR of call operand (parameter)
 463     LiveRange *const LR = LRI.getLiveRangeForValue(CallArg);
 464
 465     // not possible to have a null LR since all args (even consts)
 466     // must be defined before
 467     if( !LR ) {
 468       if( DEBUG_RA) {
 469         cerr << " ERROR: In call instr, no LR for arg:  " ;
 470         printValue(CallArg); cerr << "\n";
 471       }
 472       assert(0 && "NO LR for call arg");
 473       // continue;
 474     }
 475
 476     unsigned RegType = getRegType( LR );
 477
 478     // if the arg is in int class - allocate a reg for an int arg
 479     if( RegType == IntRegType ) {
 480
 481       if( argNo < NumOfIntArgRegs)
 482         LR->setSuggestedColor( SparcIntRegOrder::o0 + argNo );
 483
 484       else if (DEBUG_RA)
 485         // Do NOTHING as this will be colored as a normal value.
 486         cerr << " Regr not suggested for int call arg\n";
 487
 488     }
 489     else if( RegType == FPSingleRegType &&  (argNo*2 +1)< NumOfFloatArgRegs)
 490       LR->setSuggestedColor( SparcFloatRegOrder::f0 + (argNo * 2 + 1) );
 491
 492
 493     else if( RegType == FPDoubleRegType && (argNo*2) < NumOfFloatArgRegs)
 494       LR->setSuggestedColor( SparcFloatRegOrder::f0 + (argNo * 2) );
 495
 496
 497   } // for all call arguments
 498
 499 }
 500
 501
 502 //---------------------------------------------------------------------------
 503 // After graph coloring, we have call this method to see whehter the return
 504 // value and the call args received the correct colors. If not, we have
 505 // to instert copy instructions.
 506 //---------------------------------------------------------------------------
 507
 508 void UltraSparcRegInfo::colorCallArgs(const MachineInstr *const CallMI,
 509                                       LiveRangeInfo& LRI,
 510                                       AddedInstrns *const CallAI,
 511                                       PhyRegAlloc &PRA,
 512                                       const BasicBlock *BB) const {
 513
 514   assert ( (UltraSparcInfo->getInstrInfo()).isCall(CallMI->getOpCode()) );
 515
 516   // Reset the optional args area in the stack frame
 517   // since that is reused for each call
 518   //
 519   PRA.mcInfo.resetOptionalArgs(target);
 520
 521   // First color the return value of the call.
 522   // If there is a LR for the return value, it means this
 523   // method returns a value
 524
 525   MachineInstr *AdMI;
 526
 527   const Value *RetVal = getCallInstRetVal( CallMI );
 528
 529   if( RetVal ) {
 530
 531     LiveRange * RetValLR = LRI.getLiveRangeForValue( RetVal );
 532
 533     if( !RetValLR ) {
 534       cerr << "\nNo LR for:";
 535       printValue( RetVal );
 536       cerr << "\n";
 537       assert( RetValLR && "ERR:No LR for non-void return value");
 538       //return;
 539     }
 540
 541     unsigned RegClassID = (RetValLR->getRegClass())->getID();
 542     bool recvCorrectColor = false;
 543
 544     unsigned CorrectCol;                // correct color for ret value
 545     if(RegClassID == IntRegClassID)
 546       CorrectCol = SparcIntRegOrder::o0;
 547     else if(RegClassID == FloatRegClassID)
 548       CorrectCol = SparcFloatRegOrder::f0;
 549     else {
 550       assert( 0 && "Unknown RegClass");
 551       return;
 552     }
 553
 554     // if the LR received the correct color, NOTHING to do
 555
 556     if(  RetValLR->hasColor() )
 557       if( RetValLR->getColor() == CorrectCol )
 558         recvCorrectColor = true;
 559
 560
 561     // if we didn't receive the correct color for some reason,
 562     // put copy instruction
 563
 564     if( !recvCorrectColor ) {
 565
 566       unsigned RegType = getRegType( RetValLR );
 567
 568       // the  reg that LR must be colored with
 569       unsigned UniRetReg = getUnifiedRegNum( RegClassID, CorrectCol);
 570
 571       if( RetValLR->hasColor() ) {
 572
 573         unsigned
 574           UniRetLRReg=getUnifiedRegNum(RegClassID,RetValLR->getColor());
 575
 576         // the return value is coming in UniRetReg but has to go into
 577         // the UniRetLRReg
 578
 579         AdMI = cpReg2RegMI( UniRetReg, UniRetLRReg, RegType );
 580
 581       } // if LR has color
 582       else {
 583
 584         // if the LR did NOT receive a color, we have to move the return
 585         // value coming in UniRetReg to the stack pos of spilled LR
 586
 587         AdMI =  cpReg2MemMI(UniRetReg, getFramePointer(),
 588                             RetValLR->getSpillOffFromFP(), RegType );
 589       }
 590
 591       CallAI->InstrnsAfter.push_back( AdMI );
 592
 593     } // the LR didn't receive the suggested color
 594
 595   } // if there a return value
 596
 597
 598   //-------------------------------------------
 599   // Now color all args of the call instruction
 600   //-------------------------------------------
 601
 602   std::vector<MachineInstr *> AddedInstrnsBefore;
 603
 604   unsigned NumOfCallArgs =  getCallInstNumArgs( CallMI );
 605
 606   bool VarArgCall = isVarArgCall( CallMI );
 607
 608   if(VarArgCall) cerr << "\nVar arg call found!!\n";
 609
 610   for(unsigned argNo=0, i=0; i < NumOfCallArgs; ++i, ++argNo ) {
 611
 612     const Value *CallArg = CallMI->getImplicitRef(i);
 613
 614     // get the LR of call operand (parameter)
 615     LiveRange *const LR = LRI.getLiveRangeForValue(CallArg);
 616
 617     unsigned RegType = getRegType( CallArg );
 618     unsigned RegClassID =  getRegClassIDOfValue( CallArg);
 619
 620     // find whether this argument is coming in a register (if not, on stack)
 621
 622     bool isArgInReg = false;
 623     unsigned UniArgReg = InvalidRegNum;  // reg that LR must be colored with
 624
 625     if( (RegType== IntRegType && argNo <  NumOfIntArgRegs)) {
 626       isArgInReg = true;
 627       UniArgReg = getUnifiedRegNum(RegClassID, SparcIntRegOrder::o0 + argNo );
 628     }
 629     else if(RegType == FPSingleRegType && argNo < NumOfFloatArgRegs)  {
 630       isArgInReg = true;
 631
 632       if( !VarArgCall )
 633         UniArgReg = getUnifiedRegNum(RegClassID,
 634                                      SparcFloatRegOrder::f0 + (argNo*2 + 1) );
 635       else {
 636         // a variable argument call - must pass float arg in %o's
 637         if( argNo <  NumOfIntArgRegs)
 638           UniArgReg=getUnifiedRegNum(IntRegClassID,SparcIntRegOrder::o0+argNo);
 639         else
 640           isArgInReg = false;
 641       }
 642
 643     }
 644     else if(RegType == FPDoubleRegType && argNo < NumOfFloatArgRegs)  {
 645       isArgInReg = true;
 646
 647       if( !VarArgCall )
 648         UniArgReg =getUnifiedRegNum(RegClassID,SparcFloatRegOrder::f0+argNo*2);
 649       else {
 650         // a variable argument call - must pass float arg in %o's
 651         if( argNo <  NumOfIntArgRegs)
 652           UniArgReg=getUnifiedRegNum(IntRegClassID,SparcIntRegOrder::o0+argNo);
 653         else
 654           isArgInReg = false;
 655       }
 656     }
 657
 658     // not possible to have a null LR since all args (even consts)
 659     // must be defined before
 660     if( !LR ) {
 661       if( DEBUG_RA) {
 662         cerr << " ERROR: In call instr, no LR for arg:  " ;
 663         printValue(CallArg); cerr << "\n";
 664       }
 665       assert(0 && "NO LR for call arg");
 666       // continue;
 667     }
 668
 669
 670     if( LR->hasColor() ) {
 671
 672
 673       unsigned UniLRReg = getUnifiedRegNum( RegClassID,  LR->getColor() );
 674
 675       // if LR received the correct color, nothing to do
 676       if( UniLRReg == UniArgReg )
 677         continue;
 678
 679       // We are here because though the LR is allocated a register, it
 680       // was not allocated the suggested register. So, we have to copy %ix reg
 681       // (or stack pos of arg) to the register it was colored with
 682
 683       // the LR is colored with UniLRReg but has to go into  UniArgReg
 684       // to pass it as an argument
 685
 686       if( isArgInReg ) {
 687
 688         if( VarArgCall && RegClassID == FloatRegClassID ) {
 689
 690
 691           // for a variable argument call, the float reg must go in a %o reg.
 692           // We have to move a float reg to an int reg via memory.
 693           // The store instruction will be directly added to
 694           // CallAI->InstrnsBefore since it does not need reordering
 695           //
 696           int TmpOff = PRA.mcInfo.pushTempValue(target,
 697                                                getSpilledRegSize(RegType));
 698
 699           AdMI = cpReg2MemMI(UniLRReg, getFramePointer(), TmpOff, RegType );
 700           CallAI->InstrnsBefore.push_back( AdMI );
 701
 702           AdMI = cpMem2RegMI(getFramePointer(), TmpOff, UniArgReg, IntRegType);
 703           AddedInstrnsBefore.push_back( AdMI );
 704         }
 705
 706         else {
 707           AdMI = cpReg2RegMI(UniLRReg, UniArgReg, RegType );
 708           AddedInstrnsBefore.push_back( AdMI );
 709         }
 710
 711       }
 712
 713       else {
 714         // Now, we have to pass the arg on stack. Since LR received a register
 715         // we just have to move that register to the stack position where
 716         // the argument must be passed
 717
 718         int argOffset = PRA.mcInfo.allocateOptionalArg(target, LR->getType());
 719
 720         AdMI = cpReg2MemMI(UniLRReg, getStackPointer(), argOffset, RegType );
 721
 722         // Now add the instruction. We can directly add to
 723         // CallAI->InstrnsBefore since we are just saving a reg on stack
 724         //
 725         CallAI->InstrnsBefore.push_back( AdMI );
 726
 727         //cerr << "\nCaution: Passing a reg on stack";
 728       }
 729
 730
 731     }
 732
 733     else {                          // LR is not colored (i.e., spilled)
 734
 735       if( isArgInReg ) {
 736
 737         // Now the LR did NOT recieve a register but has a stack poistion.
 738         // Since, the outgoing arg goes in a register we just have to insert
 739         // a load instruction to load the LR to outgoing register
 740
 741         if( VarArgCall && RegClassID == FloatRegClassID )
 742           AdMI = cpMem2RegMI(getFramePointer(), LR->getSpillOffFromFP(),
 743                              UniArgReg, IntRegType );
 744         else
 745           AdMI = cpMem2RegMI(getFramePointer(), LR->getSpillOffFromFP(),
 746                              UniArgReg, RegType );
 747
 748         cerr << "\nCaution: Loading a spilled val to a reg as a call arg";
 749         AddedInstrnsBefore.push_back( AdMI );  // Now add the instruction
 750       }
 751
 752       else {
 753         // Now, we have to pass the arg on stack. Since LR  also did NOT
 754         // receive a register we have to move an argument in memory to
 755         // outgoing parameter on stack.
 756
 757         // Optoimize: Optimize when reverse pointers in MahineInstr are
 758         // introduced.
 759         // call PRA.getUnusedRegAtMI(....) to get an unused reg. Only if this
 760         // fails, then use the following code. Currently, we cannot call the
 761         // above method since we cannot find LVSetBefore without the BB
 762
 763         int TReg = PRA.getUniRegNotUsedByThisInst( LR->getRegClass(), CallMI );
 764
 765         int TmpOff = PRA.mcInfo.pushTempValue(target,
 766                                     getSpilledRegSize(getRegType(LR)) );
 767
 768
 769         int argOffset = PRA.mcInfo.allocateOptionalArg(target, LR->getType());
 770
 771         MachineInstr *Ad1, *Ad2, *Ad3, *Ad4;
 772
 773         // Sequence:
 774         // (1) Save TReg on stack
 775         // (2) Load LR value into TReg from stack pos of LR
 776         // (3) Store Treg on outgoing Arg pos on stack
 777         // (4) Load the old value of TReg from stack to TReg (restore it)
 778
 779         Ad1 = cpReg2MemMI(TReg, getFramePointer(), TmpOff, RegType );
 780         Ad2 = cpMem2RegMI(getFramePointer(), LR->getSpillOffFromFP(),
 781                           TReg, RegType );
 782         Ad3 = cpReg2MemMI(TReg, getStackPointer(), argOffset, RegType );
 783         Ad4 = cpMem2RegMI(getFramePointer(), TmpOff, TReg, RegType );
 784
 785         // We directly add to CallAI->InstrnsBefore instead of adding to
 786         // AddedInstrnsBefore since these instructions must not be
 787         // reordered.
 788
 789         CallAI->InstrnsBefore.push_back( Ad1 );
 790         CallAI->InstrnsBefore.push_back( Ad2 );
 791         CallAI->InstrnsBefore.push_back( Ad3 );
 792         CallAI->InstrnsBefore.push_back( Ad4 );
 793
 794         cerr << "\nCaution: Call arg moved from stack2stack for: " << *CallMI ;
 795       }
 796
 797     }
 798
 799   }  // for each parameter in call instruction
 800
 801
 802   // if we added any instruction before the call instruction, verify
 803   // that they are in the proper order and if not, reorder them
 804
 805   if( ! AddedInstrnsBefore.empty() ) {
 806
 807     if( DEBUG_RA  ) {
 808       cerr << "\nCalling reorder with instrns: \n";
 809       for(unsigned i=0; i < AddedInstrnsBefore.size(); i++)
 810         cerr  << *(AddedInstrnsBefore[i]);
 811     }
 812
 813     std::vector<MachineInstr *> TmpVec;
 814     OrderAddedInstrns(AddedInstrnsBefore, TmpVec, PRA);
 815
 816     if( DEBUG_RA   ) {
 817       cerr << "\nAfter reordering instrns: \n";
 818       for(unsigned i=0; i < TmpVec.size(); i++)
 819         cerr << *(TmpVec[i]);
 820     }
 821
 822     // copy the results back from TmpVec to InstrnsBefore
 823     for(unsigned i=0; i < TmpVec.size(); i++)
 824       CallAI->InstrnsBefore.push_back( TmpVec[i] );
 825   }
 826
 827
 828   // now insert caller saving code for this call instruction
 829   //
 830   insertCallerSavingCode(CallMI, BB, PRA);
 831
 832
 833   // Reset optional args area again to be safe
 834   PRA.mcInfo.resetOptionalArgs(target);
 835
 836
 837 }
 838
 839 //---------------------------------------------------------------------------
 840 // This method is called for an LLVM return instruction to identify which
 841 // values will be returned from this method and to suggest colors.
 842 //---------------------------------------------------------------------------
 843 void UltraSparcRegInfo::suggestReg4RetValue(const MachineInstr *const RetMI,
 844                                              LiveRangeInfo& LRI) const {
 845
 846   assert( (UltraSparcInfo->getInstrInfo()).isReturn( RetMI->getOpCode() ) );
 847
 848     suggestReg4RetAddr(RetMI, LRI);
 849
 850   // if there is an implicit ref, that has to be the ret value
 851   if(  RetMI->getNumImplicitRefs() > 0 ) {
 852
 853     // The first implicit operand is the return value of a return instr
 854     const Value *RetVal =  RetMI->getImplicitRef(0);
 855
 856     LiveRange *const LR = LRI.getLiveRangeForValue( RetVal );
 857
 858     if( !LR ) {
 859      cerr << "\nNo LR for:";
 860      printValue( RetVal );
 861      cerr << "\n";
 862      assert( LR && "No LR for return value of non-void method");
 863      //return;
 864    }
 865
 866     unsigned RegClassID = (LR->getRegClass())->getID();
 867
 868     if( RegClassID == IntRegClassID )
 869       LR->setSuggestedColor(SparcIntRegOrder::i0);
 870
 871     else if ( RegClassID == FloatRegClassID )
 872       LR->setSuggestedColor(SparcFloatRegOrder::f0);
 873
 874   }
 875
 876 }
 877
 878
 879
 880 //---------------------------------------------------------------------------
 881 // Colors the return value of a method to %i0 or %f0, if possible. If it is
 882 // not possilbe to directly color the LR, insert a copy instruction to move
 883 // the LR to %i0 or %f0. When the LR is spilled, instead of the copy, we
 884 // have to put a load instruction.
 885 //---------------------------------------------------------------------------
 886 void UltraSparcRegInfo::colorRetValue(const  MachineInstr *const RetMI,
 887                                       LiveRangeInfo& LRI,
 888                                       AddedInstrns *const RetAI) const {
 889
 890   assert( (UltraSparcInfo->getInstrInfo()).isReturn( RetMI->getOpCode() ) );
 891
 892   // if there is an implicit ref, that has to be the ret value
 893   if(  RetMI->getNumImplicitRefs() > 0 ) {
 894
 895     // The first implicit operand is the return value of a return instr
 896     const Value *RetVal =  RetMI->getImplicitRef(0);
 897
 898     LiveRange *const LR = LRI.getLiveRangeForValue( RetVal );
 899
 900     if( ! LR ) {
 901         cerr << "\nNo LR for:";
 902         printValue( RetVal );
 903         cerr << "\n";
 904         // assert( LR && "No LR for return value of non-void method");
 905         return;
 906     }
 907
 908     unsigned RegClassID =  getRegClassIDOfValue(RetVal);
 909     unsigned RegType = getRegType( RetVal );
 910
 911     unsigned CorrectCol;
 912     if(RegClassID == IntRegClassID)
 913       CorrectCol = SparcIntRegOrder::i0;
 914     else if(RegClassID == FloatRegClassID)
 915       CorrectCol = SparcFloatRegOrder::f0;
 916     else {
 917       assert( 0 && "Unknown RegClass");
 918       return;
 919     }
 920
 921     // if the LR received the correct color, NOTHING to do
 922
 923     if(  LR->hasColor() )
 924       if( LR->getColor() == CorrectCol )
 925         return;
 926
 927     unsigned UniRetReg =  getUnifiedRegNum( RegClassID, CorrectCol );
 928
 929     if( LR->hasColor() ) {
 930
 931       // We are here because the LR was allocted a regiter
 932       // It may be the suggested register or not
 933
 934       // copy the LR of retun value to i0 or f0
 935
 936       unsigned UniLRReg =getUnifiedRegNum( RegClassID, LR->getColor());
 937
 938       // the LR received  UniLRReg but must be colored with UniRetReg
 939       // to pass as the return value
 940       RetAI->InstrnsBefore.push_back(cpReg2RegMI(UniLRReg, UniRetReg, RegType));
 941     }
 942     else {                              // if the LR is spilled
 943       MachineInstr *AdMI = cpMem2RegMI(getFramePointer(),
 944                                        LR->getSpillOffFromFP(),
 945                                        UniRetReg, RegType);
 946       RetAI->InstrnsBefore.push_back(AdMI);
 947       cerr << "\nCopied the return value from stack\n";
 948     }
 949
 950   } // if there is a return value
 951
 952 }
 953
 954
 955 //---------------------------------------------------------------------------
 956 // Copy from a register to register. Register number must be the unified
 957 // register number
 958 //---------------------------------------------------------------------------
 959
 960 MachineInstr * UltraSparcRegInfo::cpReg2RegMI(const unsigned SrcReg,
 961                                               const unsigned DestReg,
 962                                               const int RegType) const {
 963
 964   assert( ((int)SrcReg != InvalidRegNum) && ((int)DestReg != InvalidRegNum) &&
 965           "Invalid Register");
 966
 967   MachineInstr * MI = NULL;
 968
 969   switch( RegType ) {
 970
 971   case IntRegType:
 972   case IntCCRegType:
 973   case FloatCCRegType:
 974     MI = new MachineInstr(ADD, 3);
 975     MI->SetMachineOperand(0, SrcReg, false);
 976     MI->SetMachineOperand(1, SparcIntRegOrder::g0, false);
 977     MI->SetMachineOperand(2, DestReg, true);
 978     break;
 979
 980   case FPSingleRegType:
 981     MI = new MachineInstr(FMOVS, 2);
 982     MI->SetMachineOperand(0, SrcReg, false);
 983     MI->SetMachineOperand(1, DestReg, true);
 984     break;
 985
 986   case FPDoubleRegType:
 987     MI = new MachineInstr(FMOVD, 2);
 988     MI->SetMachineOperand(0, SrcReg, false);
 989     MI->SetMachineOperand(1, DestReg, true);
 990     break;
 991
 992   default:
 993     assert(0 && "Unknow RegType");
 994   }
 995
 996   return MI;
 997 }
 998
 999
1000 //---------------------------------------------------------------------------
1001 // Copy from a register to memory (i.e., Store). Register number must
1002 // be the unified register number
1003 //---------------------------------------------------------------------------
1004
1005
1006 MachineInstr * UltraSparcRegInfo::cpReg2MemMI(const unsigned SrcReg,
1007                                               const unsigned DestPtrReg,
1008                                               const int Offset,
1009                                               const int RegType) const {
1010
1011
1012   MachineInstr * MI = NULL;
1013
1014   switch( RegType ) {
1015
1016   case IntRegType:
1017   case FloatCCRegType:
1018     MI = new MachineInstr(STX, 3);
1019     MI->SetMachineOperand(0, SrcReg, false);
1020     MI->SetMachineOperand(1, DestPtrReg, false);
1021     MI->SetMachineOperand(2, MachineOperand:: MO_SignExtendedImmed,
1022                           (int64_t) Offset, false);
1023     break;
1024
1025   case FPSingleRegType:
1026     MI = new MachineInstr(ST, 3);
1027     MI->SetMachineOperand(0, SrcReg, false);
1028     MI->SetMachineOperand(1, DestPtrReg, false);
1029     MI->SetMachineOperand(2, MachineOperand:: MO_SignExtendedImmed,
1030                           (int64_t) Offset, false);
1031     break;
1032
1033   case FPDoubleRegType:
1034     MI = new MachineInstr(STD, 3);
1035     MI->SetMachineOperand(0, SrcReg, false);
1036     MI->SetMachineOperand(1, DestPtrReg, false);
1037     MI->SetMachineOperand(2, MachineOperand:: MO_SignExtendedImmed,
1038                           (int64_t) Offset, false);
1039     break;
1040
1041   case IntCCRegType:
1042     assert( 0 && "Cannot directly store %ccr to memory");
1043
1044   default:
1045     assert(0 && "Unknow RegType in cpReg2MemMI");
1046   }
1047
1048   return MI;
1049 }
1050
1051
1052 //---------------------------------------------------------------------------
1053 // Copy from memory to a reg (i.e., Load) Register number must be the unified
1054 // register number
1055 //---------------------------------------------------------------------------
1056
1057
1058 MachineInstr * UltraSparcRegInfo::cpMem2RegMI(const unsigned SrcPtrReg,
1059                                               const int Offset,
1060                                               const unsigned DestReg,
1061                                               const int RegType) const {
1062
1063   MachineInstr * MI = NULL;
1064
1065   switch( RegType ) {
1066
1067   case IntRegType:
1068   case FloatCCRegType:
1069     MI = new MachineInstr(LDX, 3);
1070     MI->SetMachineOperand(0, SrcPtrReg, false);
1071     MI->SetMachineOperand(1, MachineOperand:: MO_SignExtendedImmed,
1072                           (int64_t) Offset, false);
1073     MI->SetMachineOperand(2, DestReg, true);
1074     break;
1075
1076   case FPSingleRegType:
1077     MI = new MachineInstr(LD, 3);
1078     MI->SetMachineOperand(0, SrcPtrReg, false);
1079     MI->SetMachineOperand(1, MachineOperand:: MO_SignExtendedImmed,
1080                           (int64_t) Offset, false);
1081     MI->SetMachineOperand(2, DestReg, true);
1082
1083     break;
1084
1085   case FPDoubleRegType:
1086     MI = new MachineInstr(LDD, 3);
1087     MI->SetMachineOperand(0, SrcPtrReg, false);
1088     MI->SetMachineOperand(1, MachineOperand:: MO_SignExtendedImmed,
1089                           (int64_t) Offset, false);
1090     MI->SetMachineOperand(2, DestReg, true);
1091     break;
1092
1093   case IntCCRegType:
1094     assert( 0 && "Cannot directly load into %ccr from memory");
1095
1096   default:
1097     assert(0 && "Unknown RegType in cpMem2RegMI");
1098   }
1099
1100   return MI;
1101 }
1102
1103
1104
1105
1106
1107 //---------------------------------------------------------------------------
1108 // Generate a copy instruction to copy a value to another. Temporarily
1109 // used by PhiElimination code.
1110 //---------------------------------------------------------------------------
1111
1112
1113 MachineInstr * UltraSparcRegInfo::cpValue2Value(Value *Src, Value *Dest) const{
1114
1115   int RegType = getRegType( Src );
1116
1117   assert( (RegType==getRegType(Src))  && "Src & Dest are diff types");
1118
1119   MachineInstr * MI = NULL;
1120
1121   switch( RegType ) {
1122
1123   case IntRegType:
1124
1125     MI = new MachineInstr(ADD, 3);
1126     MI->SetMachineOperand(0, MachineOperand:: MO_VirtualRegister, Src, false);
1127     MI->SetMachineOperand(1, SparcIntRegOrder::g0, false);
1128     MI->SetMachineOperand(2, MachineOperand:: MO_VirtualRegister, Dest, true);
1129     break;
1130
1131   case FPSingleRegType:
1132     MI = new MachineInstr(FMOVS, 2);
1133     MI->SetMachineOperand(0, MachineOperand:: MO_VirtualRegister, Src, false);
1134     MI->SetMachineOperand(1, MachineOperand:: MO_VirtualRegister, Dest, true);
1135     break;
1136
1137
1138   case FPDoubleRegType:
1139     MI = new MachineInstr(FMOVD, 2);
1140     MI->SetMachineOperand(0, MachineOperand:: MO_VirtualRegister, Src, false);
1141     MI->SetMachineOperand(1, MachineOperand:: MO_VirtualRegister, Dest, true);
1142     break;
1143
1144   default:
1145     assert(0 && "Unknow RegType in CpValu2Value");
1146   }
1147
1148   return MI;
1149 }
1150
1151
1152
1153
1154
1155
1156 //----------------------------------------------------------------------------
1157 // This method inserts caller saving/restoring instructons before/after
1158 // a call machine instruction. The caller saving/restoring instructions are
1159 // inserted like:
1160 //
1161 //    ** caller saving instructions
1162 //    other instructions inserted for the call by ColorCallArg
1163 //    CALL instruction
1164 //    other instructions inserted for the call ColorCallArg
1165 //    ** caller restoring instructions
1166 //
1167 //----------------------------------------------------------------------------
1168
1169
1170 void UltraSparcRegInfo::insertCallerSavingCode(const MachineInstr *MInst,
1171                                                const BasicBlock *BB,
1172                                                PhyRegAlloc &PRA) const {
1173
1174   // has set to record which registers were saved/restored
1175   //
1176   std::hash_set<unsigned> PushedRegSet;
1177
1178   // Now find the LR of the return value of the call
1179   // The last *implicit operand* is the return value of a call
1180   // Insert it to to he PushedRegSet since we must not save that register
1181   // and restore it after the call.
1182   // We do this because, we look at the LV set *after* the instruction
1183   // to determine, which LRs must be saved across calls. The return value
1184   // of the call is live in this set - but we must not save/restore it.
1185
1186
1187   const Value *RetVal = getCallInstRetVal( MInst );
1188
1189   if( RetVal ) {
1190
1191     LiveRange *RetValLR = PRA.LRI.getLiveRangeForValue( RetVal );
1192     assert( RetValLR && "No LR for RetValue of call");
1193
1194     if(  RetValLR->hasColor())
1195       PushedRegSet.insert(
1196          getUnifiedRegNum((RetValLR->getRegClass())->getID(),
1197                                       RetValLR->getColor() ) );
1198   }
1199
1200
1201   const LiveVarSet *LVSetAft =  PRA.LVI->getLiveVarSetAfterMInst(MInst, BB);
1202
1203   LiveVarSet::const_iterator LIt = LVSetAft->begin();
1204
1205   // for each live var in live variable set after machine inst
1206   for( ; LIt != LVSetAft->end(); ++LIt) {
1207
1208    //  get the live range corresponding to live var
1209     LiveRange *const LR = PRA.LRI.getLiveRangeForValue(*LIt );
1210
1211     // LR can be null if it is a const since a const
1212     // doesn't have a dominating def - see Assumptions above
1213     if( LR )   {
1214
1215       if( LR->hasColor() ) {
1216
1217         unsigned RCID = (LR->getRegClass())->getID();
1218         unsigned Color = LR->getColor();
1219
1220         if ( isRegVolatile(RCID, Color) ) {
1221
1222           // if the value is in both LV sets (i.e., live before and after
1223           // the call machine instruction)
1224
1225           unsigned Reg = getUnifiedRegNum(RCID, Color);
1226
1227           if( PushedRegSet.find(Reg) == PushedRegSet.end() ) {
1228
1229             // if we haven't already pushed that register
1230
1231             unsigned RegType = getRegType( LR );
1232
1233             // Now get two instructions - to push on stack and pop from stack
1234             // and add them to InstrnsBefore and InstrnsAfter of the
1235             // call instruction
1236
1237
1238             int StackOff =  PRA.mcInfo.pushTempValue(target,
1239                                                getSpilledRegSize(RegType));
1240
1241
1242             MachineInstr *AdIBefCC, *AdIAftCC, *AdICpCC;
1243             MachineInstr *AdIBef, *AdIAft;
1244
1245
1246             //---- Insert code for pushing the reg on stack ----------
1247
1248             if( RegType == IntCCRegType ) {
1249
1250               // Handle IntCCRegType specially since we cannot directly
1251               // push %ccr on to the stack
1252
1253               const LiveVarSet *LVSetBef =
1254                 PRA.LVI->getLiveVarSetBeforeMInst(MInst, BB);
1255
1256               // get a free INTEGER register
1257               int FreeIntReg =
1258                 PRA.getUsableUniRegAtMI(LR->getRegClass(), IntRegType, MInst,
1259                                      LVSetBef, AdIBefCC, AdIAftCC);
1260
1261               // insert the instructions in reverse order since we are
1262               // adding them to the front of InstrnsBefore
1263
1264               if(AdIAftCC)
1265                 (PRA.AddedInstrMap[MInst]->InstrnsBefore).push_front(AdIAftCC);
1266
1267               AdICpCC = cpCCR2IntMI(FreeIntReg);
1268               (PRA.AddedInstrMap[MInst]->InstrnsBefore).push_front(AdICpCC);
1269
1270               if(AdIBefCC)
1271                 (PRA.AddedInstrMap[MInst]->InstrnsBefore).push_front(AdIBefCC);
1272
1273               if(DEBUG_RA) {
1274                 cerr << "\n!! Inserted caller saving (push) inst for %ccr:";
1275                 if(AdIBefCC) cerr << "\t" <<  *(AdIBefCC);
1276                 cerr  << "\t" << *AdICpCC;
1277                 if(AdIAftCC) cerr  << "\t" << *(AdIAftCC);
1278               }
1279
1280             } else  {
1281               // for any other register type, just add the push inst
1282               AdIBef = cpReg2MemMI(Reg, getFramePointer(), StackOff, RegType );
1283               ((PRA.AddedInstrMap[MInst])->InstrnsBefore).push_front(AdIBef);
1284             }
1285
1286
1287             //---- Insert code for popping the reg from the stack ----------
1288
1289             if( RegType == IntCCRegType ) {
1290
1291               // Handle IntCCRegType specially since we cannot directly
1292               // pop %ccr on from the stack
1293
1294               // get a free INT register
1295               int FreeIntReg =
1296                 PRA.getUsableUniRegAtMI(LR->getRegClass(), IntRegType, MInst,
1297                                      LVSetAft, AdIBefCC, AdIAftCC);
1298
1299               if(AdIBefCC)
1300                 (PRA.AddedInstrMap[MInst]->InstrnsAfter).push_back(AdIBefCC);
1301
1302               AdICpCC = cpInt2CCRMI(FreeIntReg);
1303               (PRA.AddedInstrMap[MInst]->InstrnsAfter).push_back(AdICpCC);
1304
1305               if(AdIAftCC)
1306                 (PRA.AddedInstrMap[MInst]->InstrnsAfter).push_back(AdIAftCC);
1307
1308               if(DEBUG_RA) {
1309
1310                 cerr << "\n!! Inserted caller saving (pop) inst for %ccr:";
1311                 if(AdIBefCC) cerr << "\t" <<  *(AdIBefCC);
1312                 cerr  << "\t" << *AdICpCC;
1313                 if(AdIAftCC) cerr  << "\t" << *(AdIAftCC);
1314               }
1315
1316             } else {
1317               // for any other register type, just add the pop inst
1318               AdIAft = cpMem2RegMI(getFramePointer(), StackOff, Reg, RegType );
1319               ((PRA.AddedInstrMap[MInst])->InstrnsAfter).push_back(AdIAft);
1320             }
1321
1322             PushedRegSet.insert( Reg );
1323
1324             if(DEBUG_RA) {
1325               cerr << "\nFor call inst:" << *MInst;
1326               cerr << " -inserted caller saving instrs:\n\t ";
1327               if( RegType == IntCCRegType )
1328                 cerr << *AdIBefCC << "\t" << *AdIAftCC  ;
1329               else
1330                 cerr << *AdIBef   << "\t" << *AdIAft    ;
1331             }
1332           } // if not already pushed
1333
1334         } // if LR has a volatile color
1335
1336       } // if LR has color
1337
1338     } // if there is a LR for Var
1339
1340   } // for each value in the LV set after instruction
1341
1342 }
1343
1344 //---------------------------------------------------------------------------
1345 // Copies %ccr into an integer register. IntReg is the UNIFIED register
1346 // number.
1347 //---------------------------------------------------------------------------
1348
1349 MachineInstr * UltraSparcRegInfo::cpCCR2IntMI(const unsigned IntReg) const {
1350   MachineInstr * MI = NULL;
1351
1352   MI = new MachineInstr(RDCCR, 2);
1353   MI->SetMachineOperand(0, SparcIntCCRegOrder::ccr, false);
1354   MI->SetMachineOperand(1, IntReg, true);
1355
1356   return MI;
1357 }
1358
1359 //---------------------------------------------------------------------------
1360 // Copies an integer register into  %ccr. IntReg is the UNIFIED register
1361 // number.
1362 //---------------------------------------------------------------------------
1363
1364 MachineInstr * UltraSparcRegInfo::cpInt2CCRMI(const unsigned IntReg) const {
1365   MachineInstr * MI = NULL;
1366
1367   MI = new MachineInstr(WRCCR, 3);
1368   MI->SetMachineOperand(0, IntReg, false);
1369   MI->SetMachineOperand(1, SparcIntRegOrder::g0, false);
1370   MI->SetMachineOperand(2, SparcIntCCRegOrder::ccr, true);
1371
1372   return MI;
1373 }
1374
1375
1376
1377
1378 //---------------------------------------------------------------------------
1379 // Print the register assigned to a LR
1380 //---------------------------------------------------------------------------
1381
1382 void UltraSparcRegInfo::printReg(const LiveRange *const LR) {
1383
1384   unsigned RegClassID = (LR->getRegClass())->getID();
1385
1386   cerr << " *Node " << (LR->getUserIGNode())->getIndex();
1387
1388   if( ! LR->hasColor() ) {
1389     cerr << " - could not find a color\n";
1390     return;
1391   }
1392
1393   // if a color is found
1394
1395   cerr << " colored with color "<< LR->getColor();
1396
1397   if( RegClassID == IntRegClassID ) {
1398     cerr<< " [" << SparcIntRegOrder::getRegName(LR->getColor()) << "]\n";
1399
1400   } else if ( RegClassID == FloatRegClassID) {
1401     cerr << "[" << SparcFloatRegOrder::getRegName(LR->getColor());
1402     if( LR->getTypeID() == Type::DoubleTyID )
1403       cerr << "+" << SparcFloatRegOrder::getRegName(LR->getColor()+1);
1404     cerr << "]\n";
1405   }
1406 }
1407
1408 //---------------------------------------------------------------------------
1409 // This method examines instructions inserted by RegAlloc code before a
1410 // machine instruction to detect invalid orders that destroy values before
1411 // they are used. If it detects such conditions, it reorders the instructions.
1412 //
1413 // The unordered instructions come in the UnordVec. These instructions are
1414 // instructions inserted by RegAlloc. All such instruction MUST have
1415 // their USES BEFORE THE DEFS after reordering.
1416
1417 // The UnordVec & OrdVec must be DISTINCT. The OrdVec must be empty when
1418 // this method is called.
1419
1420 // This method uses two vectors for efficiency in accessing
1421
1422 // Since instructions are inserted in RegAlloc, this assumes that the
1423 // first operand is the source reg and the last operand is the dest reg.
1424
1425 // All the uses are before THE def to a register
1426
1427
1428 //---------------------------------------------------------------------------
1429 void UltraSparcRegInfo::OrderAddedInstrns(std::vector<MachineInstr *> &UnordVec,
1430                                           std::vector<MachineInstr *> &OrdVec,
1431                                           PhyRegAlloc &PRA) const{
1432
1433   /*
1434     Problem: We can have instructions inserted by RegAlloc like
1435     1. add %ox %g0 %oy
1436     2. add %oy %g0 %oz, where z!=x or z==x
1437
1438     This is wrong since %oy used by 2 is overwritten by 1
1439
1440     Solution:
1441     We re-order the instructions so that the uses are before the defs
1442
1443     Algorithm:
1444
1445     do
1446       for each instruction 'DefInst' in the UnOrdVec
1447          for each instruction 'UseInst' that follows the DefInst
1448            if the reg defined by DefInst is used by UseInst
1449              mark DefInst as not movable in this iteration
1450          If DefInst is not marked as not-movable, move DefInst to OrdVec
1451     while all instructions in DefInst are moved to OrdVec
1452
1453     For moving, we call the move2OrdVec(). It checks whether there is a def
1454     in it for the uses in the instruction to be added to OrdVec. If there
1455     are no preceding defs, it just appends the instruction. If there is a
1456     preceding def, it puts two instructions to save the reg on stack before
1457     the load and puts a restore at use.
1458
1459   */
1460
1461
1462   bool CouldMoveAll;
1463   bool DebugPrint = false;
1464
1465   do {
1466
1467     CouldMoveAll = true;
1468
1469     std::vector<MachineInstr *>::iterator DefIt = UnordVec.begin();
1470
1471     for( ; DefIt !=  UnordVec.end(); ++DefIt ) {
1472
1473       // for each instruction in the UnordVec do ...
1474
1475       MachineInstr *DefInst = *DefIt;
1476
1477       if( DefInst == NULL) continue;
1478
1479       //cerr << "\nInst in UnordVec = " <<  *DefInst;
1480
1481       // last operand is the def (unless for a store which has no def reg)
1482       MachineOperand& DefOp = DefInst->getOperand(DefInst->getNumOperands()-1);
1483
1484       if( DefOp.opIsDef() &&
1485           DefOp.getOperandType() ==  MachineOperand::MO_MachineRegister) {
1486
1487         // If the operand in DefInst is a def ...
1488
1489         bool DefEqUse = false;
1490
1491         std::vector<MachineInstr *>::iterator UseIt = DefIt;
1492         UseIt++;
1493
1494         for( ; UseIt !=  UnordVec.end(); ++UseIt ) {
1495
1496           MachineInstr *UseInst = *UseIt;
1497           if( UseInst == NULL) continue;
1498
1499           // for each inst (UseInst) that is below the DefInst do ...
1500
1501
1502           MachineOperand& UseOp = UseInst->getOperand(0);
1503
1504           if( ! UseOp.opIsDef() &&
1505               UseOp.getOperandType() == MachineOperand::MO_MachineRegister) {
1506
1507             // if use is a register ...
1508
1509             if( DefOp.getMachineRegNum() == UseOp.getMachineRegNum() ) {
1510
1511               // if Def and this use are the same, it means that this use
1512               // is destroyed by a def before it is used
1513
1514               // cerr << "\nCouldn't move " << *DefInst;
1515
1516               DefEqUse = true;
1517               CouldMoveAll = false;
1518               DebugPrint = true;
1519               break;
1520             } // if two registers are equal
1521
1522           } // if use is a register
1523
1524         }// for all use instructions
1525
1526         if( ! DefEqUse ) {
1527
1528           // after examining all the instructions that follow the DefInst
1529           // if there are no dependencies, we can move it to the OrdVec
1530
1531           // cerr << "Moved to Ord: " << *DefInst;
1532
1533           moveInst2OrdVec(OrdVec, DefInst, PRA);
1534
1535           //OrdVec.push_back(DefInst);
1536
1537           // mark the pos of DefInst with NULL to indicate that it is
1538           // empty
1539           *DefIt = NULL;
1540         }
1541
1542       } // if Def is a machine register
1543
1544     } // for all instructions in the UnordVec
1545
1546
1547   } while( !CouldMoveAll);
1548
1549
1550   if(DebugPrint) {
1551     cerr << "\nAdded instructions were reordered to:\n";
1552     for(unsigned int i=0; i < OrdVec.size(); i++)
1553       cerr << *(OrdVec[i]);
1554   }
1555
1556 }
1557
1558
1559
1560
1561
1562
1563
1564
1565 void UltraSparcRegInfo::moveInst2OrdVec(std::vector<MachineInstr *> &OrdVec,
1566                                         MachineInstr *UnordInst,
1567                                         PhyRegAlloc &PRA ) const {
1568
1569   MachineOperand& UseOp = UnordInst->getOperand(0);
1570
1571   if( ! UseOp.opIsDef() &&
1572       UseOp.getOperandType() ==  MachineOperand::MO_MachineRegister) {
1573
1574     // for the use of UnordInst, see whether there is a defining instr
1575     // before in the OrdVec
1576     bool DefEqUse = false;
1577
1578     std::vector<MachineInstr *>::iterator OrdIt = OrdVec.begin();
1579
1580     for( ; OrdIt !=  OrdVec.end(); ++OrdIt ) {
1581
1582       MachineInstr *OrdInst = *OrdIt ;
1583
1584       MachineOperand& DefOp =
1585         OrdInst->getOperand(OrdInst->getNumOperands()-1);
1586
1587       if( DefOp.opIsDef() &&
1588           DefOp.getOperandType() == MachineOperand::MO_MachineRegister) {
1589
1590         //cerr << "\nDefining Ord Inst: " <<  *OrdInst;
1591
1592         if( DefOp.getMachineRegNum() == UseOp.getMachineRegNum() ) {
1593
1594           // we are here because there is a preceding def in the OrdVec
1595           // for the use in this intr we are going to insert. This
1596           // happened because the original code was like:
1597           // 1. add %ox %g0 %oy
1598           // 2. add %oy %g0 %ox
1599           // In Round1, we added 2 to OrdVec but 1 remained in UnordVec
1600           // Now we are processing %ox of 1.
1601           // We have to
1602
1603           const int UReg = DefOp.getMachineRegNum();
1604           const int RegType = getRegType(UReg);
1605           MachineInstr *AdIBef, *AdIAft;
1606
1607           const int StackOff =  PRA.mcInfo.pushTempValue(target,
1608                                          getSpilledRegSize(RegType));
1609
1610           // Save the UReg (%ox) on stack before it's destroyed
1611           AdIBef=cpReg2MemMI(UReg, getFramePointer(), StackOff, RegType);
1612           OrdIt = OrdVec.insert( OrdIt, AdIBef);
1613           OrdIt++;  // points to current instr we processed
1614
1615           // Load directly into DReg (%oy)
1616           MachineOperand&  DOp=
1617             (UnordInst->getOperand(UnordInst->getNumOperands()-1));
1618           assert(DOp.opIsDef() && "Last operand is not the def");
1619           const int DReg = DOp.getMachineRegNum();
1620
1621           AdIAft=cpMem2RegMI(getFramePointer(), StackOff, DReg, RegType);
1622           OrdVec.push_back(AdIAft);
1623
1624           cerr << "\nFixed CIRCULAR references by reordering";
1625
1626           if( DEBUG_RA ) {
1627             cerr << "\nBefore CIRCULAR Reordering:\n";
1628             cerr << *UnordInst;
1629             cerr << *OrdInst;
1630
1631             cerr << "\nAfter CIRCULAR Reordering - All Inst so far:\n";
1632             for(unsigned i=0; i < OrdVec.size(); i++)
1633               cerr << *(OrdVec[i]);
1634           }
1635
1636           // Do not copy the UseInst to OrdVec
1637           DefEqUse = true;
1638           break;
1639
1640         }// if two registers are equal
1641
1642       } // if Def is a register
1643
1644     } // for each instr in OrdVec
1645
1646     if( !DefEqUse ) {
1647
1648       // We didn't find a def in the OrdVec, so just append this inst
1649       OrdVec.push_back( UnordInst );
1650       //cerr << "Reordered Inst (Moved Dn): " <<  *UnordInst;
1651     }
1652
1653   }// if the operand in UnordInst is a use
1654
1655 }
1656
1657
1658
1659
1660
1661