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