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