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