lib/Target/SparcV9/SparcV9RegInfo.cpp

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