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       AddedInstrnsBefore.push_back( AdMI );  // Now add the instruction
 672     }
 673
 674     else {                          // LR is not colored (i.e., spilled)
 675
 676       if( isArgInReg ) {
 677
 678         // Now the LR did NOT recieve a register but has a stack poistion.
 679         // Since, the outgoing arg goes in a register we just have to insert
 680         // a load instruction to load the LR to outgoing register
 681
 682
 683         AdMI = cpMem2RegMI(getFramePointer(), LR->getSpillOffFromFP(),
 684                            UniArgReg, RegType );
 685
 686         AddedInstrnsBefore.push_back( AdMI );  // Now add the instruction
 687       }
 688
 689       else {
 690         // Now, we have to pass the arg on stack. Since LR  also did NOT
 691         // receive a register we have to move an argument in memory to
 692         // outgoing parameter on stack.
 693
 694         // Optoimize: Optimize when reverse pointers in MahineInstr are
 695         // introduced.
 696         // call PRA.getUnusedRegAtMI(....) to get an unused reg. Only if this
 697         // fails, then use the following code. Currently, we cannot call the
 698         // above method since we cannot find LVSetBefore without the BB
 699
 700         int TReg = PRA.getRegNotUsedByThisInst( LR->getRegClass(), CallMI );
 701
 702         int TmpOff = PRA.mcInfo.pushTempValue(target,
 703                               target.findOptimalStorageSize(LR->getType()));
 704                   // getStackOffsets().getNewTmpPosOffFromFP();
 705
 706         int argOffset = PRA.mcInfo.allocateOptionalArg(target, LR->getType());
 707
 708         MachineInstr *Ad1, *Ad2, *Ad3, *Ad4;
 709
 710         // Sequence:
 711         // (1) Save TReg on stack
 712         // (2) Load LR value into TReg from stack pos of LR
 713         // (3) Store Treg on outgoing Arg pos on stack
 714         // (4) Load the old value of TReg from stack to TReg (restore it)
 715
 716         Ad1 = cpReg2MemMI(TReg, getFramePointer(), TmpOff, RegType );
 717         Ad2 = cpMem2RegMI(getFramePointer(), LR->getSpillOffFromFP(),
 718                           TReg, RegType );
 719         Ad3 = cpReg2MemMI(TReg, getStackPointer(), argOffset, RegType );
 720         Ad4 = cpMem2RegMI(getFramePointer(), TmpOff, TReg, RegType );
 721
 722         // We directly add to CallAI->InstrnsBefore instead of adding to
 723         // AddedInstrnsBefore since these instructions must not be
 724         // reordered.
 725
 726         CallAI->InstrnsBefore.push_back( Ad1 );
 727         CallAI->InstrnsBefore.push_back( Ad2 );
 728         CallAI->InstrnsBefore.push_back( Ad3 );
 729         CallAI->InstrnsBefore.push_back( Ad4 );
 730
 731         cerr << "\n Caution: Call arg moved from stack to stack";
 732       }
 733
 734     }
 735
 736   }  // for each parameter in call instruction
 737
 738
 739   // if we added any instruction before the call instruction, verify
 740   // that they are in the proper order and if not, reorder them
 741
 742   if( ! AddedInstrnsBefore.empty() ) {
 743
 744     if( DEBUG_RA  ) {
 745       cerr << "\nCalling reorder with instrns: \n";
 746       for(unsigned i=0; i < AddedInstrnsBefore.size(); i++)
 747         cerr  << *(AddedInstrnsBefore[i]);
 748     }
 749
 750     vector <MachineInstr *> TmpVec;
 751     OrderAddedInstrns(AddedInstrnsBefore, TmpVec, PRA);
 752
 753     if( DEBUG_RA   ) {
 754       cerr << "\nAfter reordering instrns: \n";
 755       for(unsigned i=0; i < TmpVec.size(); i++)
 756         cerr << *(TmpVec[i]);
 757     }
 758
 759     // copy the results back from TmpVec to InstrnsBefore
 760     for(unsigned i=0; i < TmpVec.size(); i++)
 761       CallAI->InstrnsBefore.push_back( TmpVec[i] );
 762   }
 763
 764
 765   // Reset optional args area again to be safe
 766   PRA.mcInfo.resetOptionalArgs(target);
 767
 768
 769 }
 770
 771 //---------------------------------------------------------------------------
 772 // This method is called for an LLVM return instruction to identify which
 773 // values will be returned from this method and to suggest colors.
 774 //---------------------------------------------------------------------------
 775 void UltraSparcRegInfo::suggestReg4RetValue(const MachineInstr *const RetMI,
 776                                              LiveRangeInfo& LRI) const {
 777
 778   assert( (UltraSparcInfo->getInstrInfo()).isReturn( RetMI->getOpCode() ) );
 779
 780     suggestReg4RetAddr(RetMI, LRI);
 781
 782   // if there is an implicit ref, that has to be the ret value
 783   if(  RetMI->getNumImplicitRefs() > 0 ) {
 784
 785     // The first implicit operand is the return value of a return instr
 786     const Value *RetVal =  RetMI->getImplicitRef(0);
 787
 788     MachineInstr *AdMI;
 789     LiveRange *const LR = LRI.getLiveRangeForValue( RetVal );
 790
 791     if( !LR ) {
 792      cerr << "\nNo LR for:";
 793      printValue( RetVal );
 794      cerr << endl;
 795      assert( LR && "No LR for return value of non-void method");
 796      //return;
 797    }
 798
 799     unsigned RegClassID = (LR->getRegClass())->getID();
 800
 801     if( RegClassID == IntRegClassID )
 802       LR->setSuggestedColor(SparcIntRegOrder::i0);
 803
 804     else if ( RegClassID == FloatRegClassID )
 805       LR->setSuggestedColor(SparcFloatRegOrder::f0);
 806
 807   }
 808
 809 }
 810
 811
 812
 813 //---------------------------------------------------------------------------
 814 // Colors the return value of a method to %i0 or %f0, if possible. If it is
 815 // not possilbe to directly color the LR, insert a copy instruction to move
 816 // the LR to %i0 or %f0. When the LR is spilled, instead of the copy, we
 817 // have to put a load instruction.
 818 //---------------------------------------------------------------------------
 819 void UltraSparcRegInfo::colorRetValue(const  MachineInstr *const RetMI,
 820                                       LiveRangeInfo& LRI,
 821                                       AddedInstrns *const RetAI) const {
 822
 823   assert( (UltraSparcInfo->getInstrInfo()).isReturn( RetMI->getOpCode() ) );
 824
 825   // if there is an implicit ref, that has to be the ret value
 826   if(  RetMI->getNumImplicitRefs() > 0 ) {
 827
 828     // The first implicit operand is the return value of a return instr
 829     const Value *RetVal =  RetMI->getImplicitRef(0);
 830
 831     MachineInstr *AdMI;
 832     LiveRange *const LR = LRI.getLiveRangeForValue( RetVal );
 833
 834     if( ! LR ) {
 835         cerr << "\nNo LR for:";
 836         printValue( RetVal );
 837         cerr << endl;
 838         // assert( LR && "No LR for return value of non-void method");
 839         return;
 840     }
 841
 842     unsigned RegClassID =  getRegClassIDOfValue(RetVal);
 843     unsigned RegType = getRegType( RetVal );
 844
 845     unsigned CorrectCol;
 846     if(RegClassID == IntRegClassID)
 847       CorrectCol = SparcIntRegOrder::i0;
 848     else if(RegClassID == FloatRegClassID)
 849       CorrectCol = SparcFloatRegOrder::f0;
 850     else {
 851       assert( 0 && "Unknown RegClass");
 852       return;
 853     }
 854
 855     // if the LR received the correct color, NOTHING to do
 856
 857     if(  LR->hasColor() )
 858       if( LR->getColor() == CorrectCol )
 859         return;
 860
 861     unsigned UniRetReg =  getUnifiedRegNum( RegClassID, CorrectCol );
 862
 863     if( LR->hasColor() ) {
 864
 865       // We are here because the LR was allocted a regiter
 866       // It may be the suggested register or not
 867
 868       // copy the LR of retun value to i0 or f0
 869
 870       unsigned UniLRReg =getUnifiedRegNum( RegClassID, LR->getColor());
 871
 872       // the LR received  UniLRReg but must be colored with UniRetReg
 873       // to pass as the return value
 874
 875       AdMI = cpReg2RegMI( UniLRReg, UniRetReg, RegType);
 876       RetAI->InstrnsBefore.push_back( AdMI );
 877     }
 878     else {                              // if the LR is spilled
 879
 880       AdMI = cpMem2RegMI(getFramePointer(), LR->getSpillOffFromFP(),
 881                          UniRetReg, RegType);
 882       RetAI->InstrnsBefore.push_back( AdMI );
 883       cout << "\nCopied the return value from stack";
 884     }
 885
 886   } // if there is a return value
 887
 888 }
 889
 890
 891 //---------------------------------------------------------------------------
 892 // Copy from a register to register. Register number must be the unified
 893 // register number
 894 //---------------------------------------------------------------------------
 895
 896
 897 MachineInstr * UltraSparcRegInfo::cpReg2RegMI(const unsigned SrcReg,
 898                                               const unsigned DestReg,
 899                                               const int RegType) const {
 900
 901   assert( ((int)SrcReg != InvalidRegNum) && ((int)DestReg != InvalidRegNum) &&
 902           "Invalid Register");
 903
 904   MachineInstr * MI = NULL;
 905
 906   switch( RegType ) {
 907
 908   case IntRegType:
 909   case IntCCRegType:
 910   case FloatCCRegType:
 911     MI = new MachineInstr(ADD, 3);
 912     MI->SetMachineOperand(0, SrcReg, false);
 913     MI->SetMachineOperand(1, SparcIntRegOrder::g0, false);
 914     MI->SetMachineOperand(2, DestReg, true);
 915     break;
 916
 917   case FPSingleRegType:
 918     MI = new MachineInstr(FMOVS, 2);
 919     MI->SetMachineOperand(0, SrcReg, false);
 920     MI->SetMachineOperand(1, DestReg, true);
 921     break;
 922
 923   case FPDoubleRegType:
 924     MI = new MachineInstr(FMOVD, 2);
 925     MI->SetMachineOperand(0, SrcReg, false);
 926     MI->SetMachineOperand(1, DestReg, true);
 927     break;
 928
 929   default:
 930     assert(0 && "Unknow RegType");
 931   }
 932
 933   return MI;
 934 }
 935
 936
 937 //---------------------------------------------------------------------------
 938 // Copy from a register to memory (i.e., Store). Register number must
 939 // be the unified register number
 940 //---------------------------------------------------------------------------
 941
 942
 943 MachineInstr * UltraSparcRegInfo::cpReg2MemMI(const unsigned SrcReg,
 944                                               const unsigned DestPtrReg,
 945                                               const int Offset,
 946                                               const int RegType) const {
 947
 948
 949   MachineInstr * MI = NULL;
 950
 951   switch( RegType ) {
 952
 953   case IntRegType:
 954   case FloatCCRegType:
 955     MI = new MachineInstr(STX, 3);
 956     MI->SetMachineOperand(0, SrcReg, false);
 957     MI->SetMachineOperand(1, DestPtrReg, false);
 958     MI->SetMachineOperand(2, MachineOperand:: MO_SignExtendedImmed,
 959                           (int64_t) Offset, false);
 960     break;
 961
 962   case FPSingleRegType:
 963     MI = new MachineInstr(ST, 3);
 964     MI->SetMachineOperand(0, SrcReg, false);
 965     MI->SetMachineOperand(1, DestPtrReg, false);
 966     MI->SetMachineOperand(2, MachineOperand:: MO_SignExtendedImmed,
 967                           (int64_t) Offset, false);
 968     break;
 969
 970   case FPDoubleRegType:
 971     MI = new MachineInstr(STD, 3);
 972     MI->SetMachineOperand(0, SrcReg, false);
 973     MI->SetMachineOperand(1, DestPtrReg, false);
 974     MI->SetMachineOperand(2, MachineOperand:: MO_SignExtendedImmed,
 975                           (int64_t) Offset, false);
 976     break;
 977
 978   case IntCCRegType:
 979     assert( 0 && "Cannot directly store %ccr to memory");
 980
 981   default:
 982     assert(0 && "Unknow RegType in cpReg2MemMI");
 983   }
 984
 985   return MI;
 986 }
 987
 988
 989 //---------------------------------------------------------------------------
 990 // Copy from memory to a reg (i.e., Load) Register number must be the unified
 991 // register number
 992 //---------------------------------------------------------------------------
 993
 994
 995 MachineInstr * UltraSparcRegInfo::cpMem2RegMI(const unsigned SrcPtrReg,
 996                                               const int Offset,
 997                                               const unsigned DestReg,
 998                                               const int RegType) const {
 999
1000   MachineInstr * MI = NULL;
1001
1002   switch( RegType ) {
1003
1004   case IntRegType:
1005   case FloatCCRegType:
1006     MI = new MachineInstr(LDX, 3);
1007     MI->SetMachineOperand(0, SrcPtrReg, false);
1008     MI->SetMachineOperand(1, MachineOperand:: MO_SignExtendedImmed,
1009                           (int64_t) Offset, false);
1010     MI->SetMachineOperand(2, DestReg, true);
1011     break;
1012
1013   case FPSingleRegType:
1014     MI = new MachineInstr(LD, 3);
1015     MI->SetMachineOperand(0, SrcPtrReg, false);
1016     MI->SetMachineOperand(1, MachineOperand:: MO_SignExtendedImmed,
1017                           (int64_t) Offset, false);
1018     MI->SetMachineOperand(2, DestReg, true);
1019
1020     break;
1021
1022   case FPDoubleRegType:
1023     MI = new MachineInstr(LDD, 3);
1024     MI->SetMachineOperand(0, SrcPtrReg, false);
1025     MI->SetMachineOperand(1, MachineOperand:: MO_SignExtendedImmed,
1026                           (int64_t) Offset, false);
1027     MI->SetMachineOperand(2, DestReg, true);
1028     break;
1029
1030   case IntCCRegType:
1031     assert( 0 && "Cannot directly load into %ccr from memory");
1032
1033   default:
1034     assert(0 && "Unknown RegType in cpMem2RegMI");
1035   }
1036
1037   return MI;
1038 }
1039
1040
1041
1042
1043 // Following method is Not needed now
1044
1045 MachineInstr* UltraSparcRegInfo::cpValue2Value(Value *Src, Value *Dest) const {
1046
1047   MachineInstr * MI = NULL;
1048
1049   MI = new MachineInstr(ADD, 3);
1050   MI->SetMachineOperand(0, MachineOperand:: MO_VirtualRegister, Src, false);
1051   MI->SetMachineOperand(1, SparcIntRegOrder::g0, false);
1052   MI->SetMachineOperand(2, MachineOperand:: MO_VirtualRegister, Dest, true);
1053
1054
1055   return MI;
1056
1057 }
1058
1059
1060
1061 //----------------------------------------------------------------------------
1062 // This method inserts caller saving/restoring instructons before/after
1063 // a call machine instruction.
1064 //----------------------------------------------------------------------------
1065
1066
1067 void UltraSparcRegInfo::insertCallerSavingCode(const MachineInstr *MInst,
1068                                                const BasicBlock *BB,
1069                                                PhyRegAlloc &PRA) const {
1070   // assert( (getInstrInfo()).isCall( MInst->getOpCode() ) );
1071
1072   // Clear the temp area of the stack
1073   PRA.mcInfo.popAllTempValues(target);
1074
1075   hash_set<unsigned> PushedRegSet;
1076
1077   // Now find the LR of the return value of the call
1078   // The last *implicit operand* is the return value of a call
1079   // Insert it to to he PushedRegSet since we must not save that register
1080   // and restore it after the call.
1081   // We do this because, we look at the LV set *after* the instruction
1082   // to determine, which LRs must be saved across calls. The return value
1083   // of the call is live in this set - but we must not save/restore it.
1084
1085
1086   const Value *RetVal = getCallInstRetVal( MInst );
1087
1088   if( RetVal ) {
1089
1090     LiveRange *RetValLR = PRA.LRI.getLiveRangeForValue( RetVal );
1091     assert( RetValLR && "No LR for RetValue of call");
1092
1093     if(  RetValLR->hasColor())
1094       PushedRegSet.insert(
1095          getUnifiedRegNum((RetValLR->getRegClass())->getID(),
1096                                       RetValLR->getColor() ) );
1097   }
1098
1099
1100   const LiveVarSet *LVSetAft =  PRA.LVI->getLiveVarSetAfterMInst(MInst, BB);
1101
1102   LiveVarSet::const_iterator LIt = LVSetAft->begin();
1103
1104   // for each live var in live variable set after machine inst
1105   for( ; LIt != LVSetAft->end(); ++LIt) {
1106
1107    //  get the live range corresponding to live var
1108     LiveRange *const LR = PRA.LRI.getLiveRangeForValue(*LIt );
1109
1110     // LR can be null if it is a const since a const
1111     // doesn't have a dominating def - see Assumptions above
1112     if( LR )   {
1113
1114       if( LR->hasColor() ) {
1115
1116         unsigned RCID = (LR->getRegClass())->getID();
1117         unsigned Color = LR->getColor();
1118
1119         if ( isRegVolatile(RCID, Color) ) {
1120
1121           // if the value is in both LV sets (i.e., live before and after
1122           // the call machine instruction)
1123
1124           unsigned Reg = getUnifiedRegNum(RCID, Color);
1125
1126           if( PushedRegSet.find(Reg) == PushedRegSet.end() ) {
1127
1128             // if we haven't already pushed that register
1129
1130             unsigned RegType = getRegType( LR );
1131
1132             // Now get two instructions - to push on stack and pop from stack
1133             // and add them to InstrnsBefore and InstrnsAfter of the
1134             // call instruction
1135
1136             int StackOff =  PRA.mcInfo.pushTempValue(target,
1137                               target.findOptimalStorageSize(LR->getType()));
1138
1139             MachineInstr *AdIBefCC, *AdIAftCC, *AdICpCC;
1140             MachineInstr *AdIBef, *AdIAft;
1141
1142
1143             //---- Insert code for pushing the reg on stack ----------
1144
1145             if( RegType == IntCCRegType ) {
1146
1147               // Handle IntCCRegType specially since we cannot directly
1148               // push %ccr on to the stack
1149
1150               const LiveVarSet *LVSetBef =
1151                 PRA.LVI->getLiveVarSetBeforeMInst(MInst, BB);
1152
1153               // get a free INTEGER register
1154               int FreeIntReg =
1155                 PRA.getUsableRegAtMI(LR->getRegClass(), IntRegType, MInst,
1156                                      LVSetBef, AdIBefCC, AdIAftCC);
1157
1158               // insert the instructions in reverse order since we are
1159               // adding them to the front of InstrnsBefore
1160
1161               if(AdIAftCC)
1162                 (PRA.AddedInstrMap[MInst]->InstrnsBefore).push_front(AdIAftCC);
1163
1164               AdICpCC = cpCCR2IntMI(FreeIntReg);
1165               (PRA.AddedInstrMap[MInst]->InstrnsBefore).push_front(AdICpCC);
1166
1167               if(AdIBefCC)
1168                 (PRA.AddedInstrMap[MInst]->InstrnsBefore).push_front(AdIBefCC);
1169
1170               if(DEBUG_RA) {
1171                 cerr << "\n!! Inserted caller saving (push) inst for %ccr:";
1172                 if(AdIBefCC) cerr << "\t" <<  *(AdIBefCC);
1173                 cerr  << "\t" << *AdICpCC;
1174                 if(AdIAftCC) cerr  << "\t" << *(AdIAftCC);
1175               }
1176
1177             } else  {
1178               // for any other register type, just add the push inst
1179               AdIBef = cpReg2MemMI(Reg, getFramePointer(), StackOff, RegType );
1180               ((PRA.AddedInstrMap[MInst])->InstrnsBefore).push_front(AdIBef);
1181             }
1182
1183
1184             //---- Insert code for popping the reg from the stack ----------
1185
1186             if( RegType == IntCCRegType ) {
1187
1188               // Handle IntCCRegType specially since we cannot directly
1189               // pop %ccr on from the stack
1190
1191               // get a free INT register
1192               int FreeIntReg =
1193                 PRA.getUsableRegAtMI(LR->getRegClass(), IntRegType, MInst,
1194                                      LVSetAft, AdIBefCC, AdIAftCC);
1195
1196               if(AdIBefCC)
1197                 (PRA.AddedInstrMap[MInst]->InstrnsAfter).push_back(AdIBefCC);
1198
1199               AdICpCC = cpInt2CCRMI(FreeIntReg);
1200               (PRA.AddedInstrMap[MInst]->InstrnsAfter).push_back(AdICpCC);
1201
1202               if(AdIAftCC)
1203                 (PRA.AddedInstrMap[MInst]->InstrnsAfter).push_back(AdIAftCC);
1204
1205               if(DEBUG_RA) {
1206
1207                 cerr << "\n!! Inserted caller saving (pop) inst for %ccr:";
1208                 if(AdIBefCC) cerr << "\t" <<  *(AdIBefCC);
1209                 cerr  << "\t" << *AdICpCC;
1210                 if(AdIAftCC) cerr  << "\t" << *(AdIAftCC);
1211               }
1212
1213             } else {
1214               // for any other register type, just add the pop inst
1215               AdIAft = cpMem2RegMI(getFramePointer(), StackOff, Reg, RegType );
1216               ((PRA.AddedInstrMap[MInst])->InstrnsAfter).push_back(AdIAft);
1217             }
1218
1219             PushedRegSet.insert( Reg );
1220
1221             if(DEBUG_RA) {
1222               cerr << "\nFor call inst:" << *MInst;
1223               cerr << " -inserted caller saving instrs:\n\t ";
1224               if( RegType == IntCCRegType )
1225                 cerr << *AdIBefCC << "\t" << *AdIAftCC  ;
1226               else
1227                 cerr << *AdIBef   << "\t" << *AdIAft    ;
1228             }
1229           } // if not already pushed
1230
1231         } // if LR has a volatile color
1232
1233       } // if LR has color
1234
1235     } // if there is a LR for Var
1236
1237   } // for each value in the LV set after instruction
1238
1239   // Clear the temp area of the stack
1240   PRA.mcInfo.popAllTempValues(target);
1241
1242 }
1243
1244 //---------------------------------------------------------------------------
1245 // Copies %ccr into an integer register. IntReg is the UNIFIED register
1246 // number.
1247 //---------------------------------------------------------------------------
1248
1249 MachineInstr * UltraSparcRegInfo::cpCCR2IntMI(const unsigned IntReg) const {
1250   MachineInstr * MI = NULL;
1251
1252   MI = new MachineInstr(RDCCR, 2);
1253   MI->SetMachineOperand(0, SparcIntCCRegOrder::ccr, false);
1254   MI->SetMachineOperand(1, IntReg, true);
1255
1256   return MI;
1257 }
1258
1259 //---------------------------------------------------------------------------
1260 // Copies an integer register into  %ccr. IntReg is the UNIFIED register
1261 // number.
1262 //---------------------------------------------------------------------------
1263
1264 MachineInstr * UltraSparcRegInfo::cpInt2CCRMI(const unsigned IntReg) const {
1265   MachineInstr * MI = NULL;
1266
1267   MI = new MachineInstr(WRCCR, 3);
1268   MI->SetMachineOperand(0, IntReg, false);
1269   MI->SetMachineOperand(1, SparcIntRegOrder::g0, false);
1270   MI->SetMachineOperand(2, SparcIntCCRegOrder::ccr, true);
1271
1272   return MI;
1273 }
1274
1275
1276
1277
1278 //---------------------------------------------------------------------------
1279 // Print the register assigned to a LR
1280 //---------------------------------------------------------------------------
1281
1282 void UltraSparcRegInfo::printReg(const LiveRange *const LR) {
1283
1284   unsigned RegClassID = (LR->getRegClass())->getID();
1285
1286   cerr << " *Node " << (LR->getUserIGNode())->getIndex();
1287
1288   if( ! LR->hasColor() ) {
1289     cerr << " - could not find a color" << endl;
1290     return;
1291   }
1292
1293   // if a color is found
1294
1295   cerr << " colored with color "<< LR->getColor();
1296
1297   if( RegClassID == IntRegClassID ) {
1298
1299     cerr<< " [" << SparcIntRegOrder::getRegName(LR->getColor()) ;
1300     cerr << "]" << endl;
1301   }
1302   else if ( RegClassID == FloatRegClassID) {
1303     cerr << "[" << SparcFloatRegOrder::getRegName(LR->getColor());
1304     if( LR->getTypeID() == Type::DoubleTyID )
1305       cerr << "+" << SparcFloatRegOrder::getRegName(LR->getColor()+1);
1306     cerr << "]" << endl;
1307   }
1308 }
1309
1310 //---------------------------------------------------------------------------
1311 // This method examines instructions inserted by RegAlloc code before a
1312 // machine instruction to detect invalid orders that destroy values before
1313 // they are used. If it detects such conditions, it reorders the instructions.
1314 //
1315 // The unordered instructions come in the UnordVec. These instructions are
1316 // instructions inserted by RegAlloc. All such instruction MUST have
1317 // their USES BEFORE THE DEFS after reordering.
1318
1319 // The UnordVec & OrdVec must be DISTINCT. The OrdVec must be empty when
1320 // this method is called.
1321
1322 // This method uses two vectors for efficiency in accessing
1323
1324 // Since instructions are inserted in RegAlloc, this assumes that the
1325 // first operand is the source reg and the last operand is the dest reg.
1326
1327 // All the uses are before THE def to a register
1328
1329
1330 //---------------------------------------------------------------------------
1331 void UltraSparcRegInfo::OrderAddedInstrns( vector<MachineInstr *> &UnordVec,
1332                                            vector<MachineInstr *> &OrdVec,
1333                                            PhyRegAlloc &PRA) const{
1334
1335   /*
1336     Problem: We can have instructions inserted by RegAlloc like
1337     1. add %ox %g0 %oy
1338     2. add %oy %g0 %oz, where z!=x or z==x
1339
1340     This is wrong since %oy used by 2 is overwritten by 1
1341
1342     Solution:
1343     We re-order the instructions so that the uses are before the defs
1344
1345     Algorithm:
1346
1347     do
1348       for each instruction 'DefInst' in the UnOrdVec
1349          for each instruction 'UseInst' that follows the DefInst
1350            if the reg defined by DefInst is used by UseInst
1351              mark DefInst as not movable in this iteration
1352          If DefInst is not marked as not-movable, move DefInst to OrdVec
1353     while all instructions in DefInst are moved to OrdVec
1354
1355     For moving, we call the move2OrdVec(). It checks whether there is a def
1356     in it for the uses in the instruction to be added to OrdVec. If there
1357     are no preceding defs, it just appends the instruction. If there is a
1358     preceding def, it puts two instructions to save the reg on stack before
1359     the load and puts a restore at use.
1360
1361   */
1362
1363
1364   bool CouldMoveAll;
1365   bool DebugPrint = false;
1366
1367   do {
1368
1369     CouldMoveAll = true;
1370
1371     vector<MachineInstr *>::iterator DefIt = UnordVec.begin();
1372
1373     for( ; DefIt !=  UnordVec.end(); ++DefIt ) {
1374
1375       // for each instruction in the UnordVec do ...
1376
1377       MachineInstr *DefInst = *DefIt;
1378
1379       if( DefInst == NULL) continue;
1380
1381       //cerr << "\nInst in UnordVec = " <<  *DefInst;
1382
1383       // last operand is the def (unless for a store which has no def reg)
1384       MachineOperand& DefOp = DefInst->getOperand(DefInst->getNumOperands()-1);
1385
1386       if( DefOp.opIsDef() &&
1387           DefOp.getOperandType() ==  MachineOperand::MO_MachineRegister) {
1388
1389         // If the operand in DefInst is a def ...
1390
1391         bool DefEqUse = false;
1392
1393         vector<MachineInstr *>::iterator UseIt = DefIt;
1394         UseIt++;
1395
1396         for( ; UseIt !=  UnordVec.end(); ++UseIt ) {
1397
1398           MachineInstr *UseInst = *UseIt;
1399           if( UseInst == NULL) continue;
1400
1401           // for each inst (UseInst) that is below the DefInst do ...
1402
1403
1404           MachineOperand& UseOp = UseInst->getOperand(0);
1405
1406           if( ! UseOp.opIsDef() &&
1407               UseOp.getOperandType() == MachineOperand::MO_MachineRegister) {
1408
1409             // if use is a register ...
1410
1411             if( DefOp.getMachineRegNum() == UseOp.getMachineRegNum() ) {
1412
1413               // if Def and this use are the same, it means that this use
1414               // is destroyed by a def before it is used
1415
1416               // cerr << "\nCouldn't move " << *DefInst;
1417
1418               DefEqUse = true;
1419               CouldMoveAll = false;
1420               DebugPrint = true;
1421               break;
1422             } // if two registers are equal
1423
1424           } // if use is a register
1425
1426         }// for all use instructions
1427
1428         if( ! DefEqUse ) {
1429
1430           // after examining all the instructions that follow the DefInst
1431           // if there are no dependencies, we can move it to the OrdVec
1432
1433           // cerr << "Moved to Ord: " << *DefInst;
1434
1435           moveInst2OrdVec(OrdVec, DefInst, PRA);
1436
1437           //OrdVec.push_back(DefInst);
1438
1439           // mark the pos of DefInst with NULL to indicate that it is
1440           // empty
1441           *DefIt = NULL;
1442         }
1443
1444       } // if Def is a machine register
1445
1446     } // for all instructions in the UnordVec
1447
1448
1449   } while( !CouldMoveAll);
1450
1451
1452   if(DebugPrint) {
1453     cerr << "\nAdded instructions were reordered to:\n";
1454     for(unsigned int i=0; i < OrdVec.size(); i++)
1455       cerr << *(OrdVec[i]);
1456   }
1457
1458 }
1459
1460
1461
1462
1463
1464
1465
1466
1467 void UltraSparcRegInfo::moveInst2OrdVec(vector<MachineInstr *> &OrdVec,
1468                                         MachineInstr *UnordInst,
1469                                         PhyRegAlloc &PRA ) const {
1470
1471   MachineOperand& UseOp = UnordInst->getOperand(0);
1472
1473   if( ! UseOp.opIsDef() &&
1474       UseOp.getOperandType() ==  MachineOperand::MO_MachineRegister) {
1475
1476     // for the use of UnordInst, see whether there is a defining instr
1477     // before in the OrdVec
1478     bool DefEqUse = false;
1479
1480     vector<MachineInstr *>::iterator OrdIt = OrdVec.begin();
1481
1482     for( ; OrdIt !=  OrdVec.end(); ++OrdIt ) {
1483
1484       MachineInstr *OrdInst = *OrdIt ;
1485
1486       MachineOperand& DefOp =
1487         OrdInst->getOperand(OrdInst->getNumOperands()-1);
1488
1489       if( DefOp.opIsDef() &&
1490           DefOp.getOperandType() == MachineOperand::MO_MachineRegister) {
1491
1492         //cerr << "\nDefining Ord Inst: " <<  *OrdInst;
1493
1494         if( DefOp.getMachineRegNum() == UseOp.getMachineRegNum() ) {
1495
1496           // we are here because there is a preceding def in the OrdVec
1497           // for the use in this intr we are going to insert. This
1498           // happened because the original code was like:
1499           // 1. add %ox %g0 %oy
1500           // 2. add %oy %g0 %ox
1501           // In Round1, we added 2 to OrdVec but 1 remained in UnordVec
1502           // Now we are processing %ox of 1.
1503           // We have to
1504
1505           const int UReg = DefOp.getMachineRegNum();
1506           const int RegType = getRegType(UReg);
1507           MachineInstr *AdIBef, *AdIAft;
1508
1509           // TODO: Change 8 below
1510           const int StackOff =  PRA.mcInfo.pushTempValue(target, 8);
1511
1512           // Save the UReg (%ox) on stack before it's destroyed
1513           AdIBef=cpReg2MemMI(UReg, getFramePointer(), StackOff, RegType);
1514           OrdIt = OrdVec.insert( OrdIt, AdIBef);
1515           OrdIt++;  // points to current instr we processed
1516
1517           // Load directly into DReg (%oy)
1518           MachineOperand&  DOp=
1519             (UnordInst->getOperand(UnordInst->getNumOperands()-1));
1520           assert(DOp.opIsDef() && "Last operand is not the def");
1521           const int DReg = DOp.getMachineRegNum();
1522
1523           AdIAft=cpMem2RegMI(getFramePointer(), StackOff, DReg, RegType);
1524           OrdVec.push_back(AdIAft);
1525
1526           cerr << "\nFixed CIRCULAR references by reordering";
1527
1528           if( DEBUG_RA ) {
1529             cerr << "\nBefore CIRCULAR Reordering:\n";
1530             cerr << *UnordInst;
1531             cerr << *OrdInst;
1532
1533             cerr << "\nAfter CIRCULAR Reordering - All Inst so far:\n";
1534             for(unsigned i=0; i < OrdVec.size(); i++)
1535               cerr << *(OrdVec[i]);
1536           }
1537
1538           // Do not copy the UseInst to OrdVec
1539           DefEqUse = true;
1540           break;
1541
1542         }// if two registers are equal
1543
1544       } // if Def is a register
1545
1546     } // for each instr in OrdVec
1547
1548     if( !DefEqUse ) {
1549
1550       // We didn't find a def in the OrdVec, so just append this inst
1551       OrdVec.push_back( UnordInst );
1552       //cerr << "Reordered Inst (Moved Dn): " <<  *UnordInst;
1553     }
1554
1555   }// if the operand in UnordInst is a use
1556
1557 }
1558
1559
1560
1561
1562
1563