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