lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp

   1 // $Id$
   2 //***************************************************************************
   3 // File:
   4 //      PhyRegAlloc.cpp
   5 //
   6 // Purpose:
   7 //      Register allocation for LLVM.
   8 //
   9 // History:
  10 //      9/10/01  -  Ruchira Sasanka - created.
  11 //**************************************************************************/
  12
  13 #include "llvm/CodeGen/RegisterAllocation.h"
  14 #include "llvm/CodeGen/PhyRegAlloc.h"
  15 #include "llvm/CodeGen/MachineInstr.h"
  16 #include "llvm/CodeGen/MachineCodeForMethod.h"
  17 #include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.h"
  18 #include "llvm/Analysis/LoopInfo.h"
  19 #include "llvm/Target/TargetMachine.h"
  20 #include "llvm/Target/MachineFrameInfo.h"
  21 #include "llvm/BasicBlock.h"
  22 #include "llvm/Function.h"
  23 #include "llvm/Type.h"
  24 #include "llvm/CodeGen/RegAllocCommon.h"
  25 #include <iostream>
  26 #include <math.h>
  27 using std::cerr;
  28
  29
  30 // ***TODO: There are several places we add instructions. Validate the order
  31 //          of adding these instructions.
  32
  33 cl::Enum<RegAllocDebugLevel_t> DEBUG_RA("dregalloc", cl::NoFlags,
  34   "enable register allocation debugging information",
  35   clEnumValN(RA_DEBUG_None   , "n", "disable debug output"),
  36   clEnumValN(RA_DEBUG_Normal , "y", "enable debug output"),
  37   clEnumValN(RA_DEBUG_Verbose, "v", "enable extra debug output"), 0);
  38
  39
  40 //----------------------------------------------------------------------------
  41 // RegisterAllocation pass front end...
  42 //----------------------------------------------------------------------------
  43 namespace {
  44   class RegisterAllocator : public FunctionPass {
  45     TargetMachine &Target;
  46   public:
  47     inline RegisterAllocator(TargetMachine &T) : Target(T) {}
  48
  49     const char *getPassName() const { return "Register Allocation"; }
  50
  51     bool runOnFunction(Function *F) {
  52       if (DEBUG_RA)
  53         cerr << "\n******************** Function "<< F->getName()
  54              << " ********************\n";
  55
  56       PhyRegAlloc PRA(F, Target, &getAnalysis<FunctionLiveVarInfo>(),
  57                       &getAnalysis<LoopInfo>());
  58       PRA.allocateRegisters();
  59
  60       if (DEBUG_RA) cerr << "\nRegister allocation complete!\n";
  61       return false;
  62     }
  63
  64     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  65       AU.addRequired(LoopInfo::ID);
  66       AU.addRequired(FunctionLiveVarInfo::ID);
  67     }
  68   };
  69 }
  70
  71 Pass *getRegisterAllocator(TargetMachine &T) {
  72   return new RegisterAllocator(T);
  73 }
  74
  75 //----------------------------------------------------------------------------
  76 // Constructor: Init local composite objects and create register classes.
  77 //----------------------------------------------------------------------------
  78 PhyRegAlloc::PhyRegAlloc(Function *F, const TargetMachine& tm,
  79                          FunctionLiveVarInfo *Lvi, LoopInfo *LDC)
  80                        :  TM(tm), Meth(F),
  81                           mcInfo(MachineCodeForMethod::get(F)),
  82                           LVI(Lvi), LRI(F, tm, RegClassList),
  83                           MRI(tm.getRegInfo()),
  84                           NumOfRegClasses(MRI.getNumOfRegClasses()),
  85                           LoopDepthCalc(LDC) {
  86
  87   // create each RegisterClass and put in RegClassList
  88   //
  89   for(unsigned int rc=0; rc < NumOfRegClasses; rc++)
  90     RegClassList.push_back(new RegClass(F, MRI.getMachineRegClass(rc),
  91                                         &ResColList));
  92 }
  93
  94
  95 //----------------------------------------------------------------------------
  96 // Destructor: Deletes register classes
  97 //----------------------------------------------------------------------------
  98 PhyRegAlloc::~PhyRegAlloc() {
  99   for( unsigned int rc=0; rc < NumOfRegClasses; rc++)
 100     delete RegClassList[rc];
 101
 102   AddedInstrMap.clear();
 103 }
 104
 105 //----------------------------------------------------------------------------
 106 // This method initally creates interference graphs (one in each reg class)
 107 // and IGNodeList (one in each IG). The actual nodes will be pushed later.
 108 //----------------------------------------------------------------------------
 109 void PhyRegAlloc::createIGNodeListsAndIGs() {
 110   if (DEBUG_RA) cerr << "Creating LR lists ...\n";
 111
 112   // hash map iterator
 113   LiveRangeMapType::const_iterator HMI = LRI.getLiveRangeMap()->begin();
 114
 115   // hash map end
 116   LiveRangeMapType::const_iterator HMIEnd = LRI.getLiveRangeMap()->end();
 117
 118   for (; HMI != HMIEnd ; ++HMI ) {
 119     if (HMI->first) {
 120       LiveRange *L = HMI->second;   // get the LiveRange
 121       if (!L) {
 122         if( DEBUG_RA) {
 123           cerr << "\n*?!?Warning: Null liver range found for: "
 124                << RAV(HMI->first) << "\n";
 125         }
 126         continue;
 127       }
 128                                         // if the Value * is not null, and LR
 129                                         // is not yet written to the IGNodeList
 130       if( !(L->getUserIGNode())  ) {
 131         RegClass *const RC =           // RegClass of first value in the LR
 132           RegClassList[ L->getRegClass()->getID() ];
 133
 134         RC->addLRToIG(L);              // add this LR to an IG
 135       }
 136     }
 137   }
 138
 139   // init RegClassList
 140   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 141     RegClassList[rc]->createInterferenceGraph();
 142
 143   if( DEBUG_RA)
 144     cerr << "LRLists Created!\n";
 145 }
 146
 147
 148
 149
 150 //----------------------------------------------------------------------------
 151 // This method will add all interferences at for a given instruction.
 152 // Interence occurs only if the LR of Def (Inst or Arg) is of the same reg
 153 // class as that of live var. The live var passed to this function is the
 154 // LVset AFTER the instruction
 155 //----------------------------------------------------------------------------
 156 void PhyRegAlloc::addInterference(const Value *Def,
 157                                   const ValueSet *LVSet,
 158                                   bool isCallInst) {
 159
 160   ValueSet::const_iterator LIt = LVSet->begin();
 161
 162   // get the live range of instruction
 163   //
 164   const LiveRange *const LROfDef = LRI.getLiveRangeForValue( Def );
 165
 166   IGNode *const IGNodeOfDef = LROfDef->getUserIGNode();
 167   assert( IGNodeOfDef );
 168
 169   RegClass *const RCOfDef = LROfDef->getRegClass();
 170
 171   // for each live var in live variable set
 172   //
 173   for( ; LIt != LVSet->end(); ++LIt) {
 174
 175     if (DEBUG_RA > 1)
 176       cerr << "< Def=" << RAV(Def) << ", Lvar=" << RAV(*LIt) << "> ";
 177
 178     //  get the live range corresponding to live var
 179     //
 180     LiveRange *LROfVar = LRI.getLiveRangeForValue(*LIt);
 181
 182     // LROfVar can be null if it is a const since a const
 183     // doesn't have a dominating def - see Assumptions above
 184     //
 185     if (LROfVar) {
 186       if(LROfDef == LROfVar)            // do not set interf for same LR
 187         continue;
 188
 189       // if 2 reg classes are the same set interference
 190       //
 191       if (RCOfDef == LROfVar->getRegClass()) {
 192         RCOfDef->setInterference( LROfDef, LROfVar);
 193       } else if (DEBUG_RA > 1)  {
 194         // we will not have LRs for values not explicitly allocated in the
 195         // instruction stream (e.g., constants)
 196         cerr << " warning: no live range for " << RAV(*LIt) << "\n";
 197       }
 198     }
 199   }
 200 }
 201
 202
 203
 204 //----------------------------------------------------------------------------
 205 // For a call instruction, this method sets the CallInterference flag in
 206 // the LR of each variable live int the Live Variable Set live after the
 207 // call instruction (except the return value of the call instruction - since
 208 // the return value does not interfere with that call itself).
 209 //----------------------------------------------------------------------------
 210
 211 void PhyRegAlloc::setCallInterferences(const MachineInstr *MInst,
 212                                        const ValueSet *LVSetAft) {
 213
 214   if( DEBUG_RA)
 215     cerr << "\n For call inst: " << *MInst;
 216
 217   ValueSet::const_iterator LIt = LVSetAft->begin();
 218
 219   // for each live var in live variable set after machine inst
 220   //
 221   for( ; LIt != LVSetAft->end(); ++LIt) {
 222
 223     //  get the live range corresponding to live var
 224     //
 225     LiveRange *const LR = LRI.getLiveRangeForValue(*LIt );
 226
 227     if( LR && DEBUG_RA) {
 228       cerr << "\n\tLR Aft Call: ";
 229       printSet(*LR);
 230     }
 231
 232     // LR can be null if it is a const since a const
 233     // doesn't have a dominating def - see Assumptions above
 234     //
 235     if( LR )   {
 236       LR->setCallInterference();
 237       if( DEBUG_RA) {
 238         cerr << "\n  ++Added call interf for LR: " ;
 239         printSet(*LR);
 240       }
 241     }
 242
 243   }
 244
 245   // Now find the LR of the return value of the call
 246   // We do this because, we look at the LV set *after* the instruction
 247   // to determine, which LRs must be saved across calls. The return value
 248   // of the call is live in this set - but it does not interfere with call
 249   // (i.e., we can allocate a volatile register to the return value)
 250   //
 251   if( const Value *RetVal = MRI.getCallInstRetVal( MInst )) {
 252     LiveRange *RetValLR = LRI.getLiveRangeForValue( RetVal );
 253     assert( RetValLR && "No LR for RetValue of call");
 254     RetValLR->clearCallInterference();
 255   }
 256
 257   // If the CALL is an indirect call, find the LR of the function pointer.
 258   // That has a call interference because it conflicts with outgoing args.
 259   if( const Value *AddrVal = MRI.getCallInstIndirectAddrVal( MInst )) {
 260     LiveRange *AddrValLR = LRI.getLiveRangeForValue( AddrVal );
 261     assert( AddrValLR && "No LR for indirect addr val of call");
 262     AddrValLR->setCallInterference();
 263   }
 264
 265 }
 266
 267
 268
 269
 270 //----------------------------------------------------------------------------
 271 // This method will walk thru code and create interferences in the IG of
 272 // each RegClass. Also, this method calculates the spill cost of each
 273 // Live Range (it is done in this method to save another pass over the code).
 274 //----------------------------------------------------------------------------
 275 void PhyRegAlloc::buildInterferenceGraphs()
 276 {
 277
 278   if(DEBUG_RA) cerr << "Creating interference graphs ...\n";
 279
 280   unsigned BBLoopDepthCost;
 281   for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
 282        BBI != BBE; ++BBI) {
 283
 284     // find the 10^(loop_depth) of this BB
 285     //
 286     BBLoopDepthCost = (unsigned) pow(10.0, LoopDepthCalc->getLoopDepth(*BBI));
 287
 288     // get the iterator for machine instructions
 289     //
 290     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 291     MachineCodeForBasicBlock::const_iterator MII = MIVec.begin();
 292
 293     // iterate over all the machine instructions in BB
 294     //
 295     for( ; MII != MIVec.end(); ++MII) {
 296
 297       const MachineInstr *MInst = *MII;
 298
 299       // get the LV set after the instruction
 300       //
 301       const ValueSet &LVSetAI = LVI->getLiveVarSetAfterMInst(MInst, *BBI);
 302
 303       const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
 304
 305       if( isCallInst ) {
 306         // set the isCallInterference flag of each live range wich extends
 307         // accross this call instruction. This information is used by graph
 308         // coloring algo to avoid allocating volatile colors to live ranges
 309         // that span across calls (since they have to be saved/restored)
 310         //
 311         setCallInterferences(MInst, &LVSetAI);
 312       }
 313
 314
 315       // iterate over all MI operands to find defs
 316       //
 317       for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
 318              OpE = MInst->end(); OpI != OpE; ++OpI) {
 319         if (OpI.isDef())    // create a new LR iff this operand is a def
 320           addInterference(*OpI, &LVSetAI, isCallInst);
 321
 322         // Calculate the spill cost of each live range
 323         //
 324         LiveRange *LR = LRI.getLiveRangeForValue(*OpI);
 325         if (LR) LR->addSpillCost(BBLoopDepthCost);
 326       }
 327
 328
 329       // if there are multiple defs in this instruction e.g. in SETX
 330       //
 331       if (TM.getInstrInfo().isPseudoInstr(MInst->getOpCode()))
 332         addInterf4PseudoInstr(MInst);
 333
 334
 335       // Also add interference for any implicit definitions in a machine
 336       // instr (currently, only calls have this).
 337       //
 338       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 339       if(  NumOfImpRefs > 0 ) {
 340         for(unsigned z=0; z < NumOfImpRefs; z++)
 341           if( MInst->implicitRefIsDefined(z) )
 342             addInterference( MInst->getImplicitRef(z), &LVSetAI, isCallInst );
 343       }
 344
 345
 346     } // for all machine instructions in BB
 347   } // for all BBs in function
 348
 349
 350   // add interferences for function arguments. Since there are no explict
 351   // defs in the function for args, we have to add them manually
 352   //
 353   addInterferencesForArgs();
 354
 355   if( DEBUG_RA)
 356     cerr << "Interference graphs calculted!\n";
 357
 358 }
 359
 360
 361
 362 //--------------------------------------------------------------------------
 363 // Pseudo instructions will be exapnded to multiple instructions by the
 364 // assembler. Consequently, all the opernds must get distinct registers.
 365 // Therefore, we mark all operands of a pseudo instruction as they interfere
 366 // with one another.
 367 //--------------------------------------------------------------------------
 368 void PhyRegAlloc::addInterf4PseudoInstr(const MachineInstr *MInst) {
 369
 370   bool setInterf = false;
 371
 372   // iterate over  MI operands to find defs
 373   //
 374   for (MachineInstr::const_val_op_iterator It1 = MInst->begin(),
 375          ItE = MInst->end(); It1 != ItE; ++It1) {
 376     const LiveRange *LROfOp1 = LRI.getLiveRangeForValue(*It1);
 377     assert((LROfOp1 || !It1.isDef()) && "No LR for Def in PSEUDO insruction");
 378
 379     MachineInstr::const_val_op_iterator It2 = It1;
 380     for(++It2; It2 != ItE; ++It2) {
 381       const LiveRange *LROfOp2 = LRI.getLiveRangeForValue(*It2);
 382
 383       if (LROfOp2) {
 384         RegClass *RCOfOp1 = LROfOp1->getRegClass();
 385         RegClass *RCOfOp2 = LROfOp2->getRegClass();
 386
 387         if( RCOfOp1 == RCOfOp2 ){
 388           RCOfOp1->setInterference( LROfOp1, LROfOp2 );
 389           setInterf = true;
 390         }
 391       } // if Op2 has a LR
 392     } // for all other defs in machine instr
 393   } // for all operands in an instruction
 394
 395   if (!setInterf && MInst->getNumOperands() > 2) {
 396     cerr << "\nInterf not set for any operand in pseudo instr:\n";
 397     cerr << *MInst;
 398     assert(0 && "Interf not set for pseudo instr with > 2 operands" );
 399   }
 400 }
 401
 402
 403
 404 //----------------------------------------------------------------------------
 405 // This method will add interferences for incoming arguments to a function.
 406 //----------------------------------------------------------------------------
 407 void PhyRegAlloc::addInterferencesForArgs() {
 408   // get the InSet of root BB
 409   const ValueSet &InSet = LVI->getInSetOfBB(Meth->front());
 410
 411   // get the argument list
 412   const Function::ArgumentListType &ArgList = Meth->getArgumentList();
 413
 414   // get an iterator to arg list
 415   Function::ArgumentListType::const_iterator ArgIt = ArgList.begin();
 416
 417
 418   for( ; ArgIt != ArgList.end() ; ++ArgIt) {  // for each argument
 419     addInterference((Value*)*ArgIt, &InSet, false);// add interferences between
 420                                               // args and LVars at start
 421     if( DEBUG_RA > 1)
 422       cerr << " - %% adding interference for  argument "
 423            << RAV((const Value *)*ArgIt) << "\n";
 424   }
 425 }
 426
 427
 428 //----------------------------------------------------------------------------
 429 // This method is called after register allocation is complete to set the
 430 // allocated reisters in the machine code. This code will add register numbers
 431 // to MachineOperands that contain a Value. Also it calls target specific
 432 // methods to produce caller saving instructions. At the end, it adds all
 433 // additional instructions produced by the register allocator to the
 434 // instruction stream.
 435 //----------------------------------------------------------------------------
 436
 437 //-----------------------------
 438 // Utility functions used below
 439 //-----------------------------
 440 inline void
 441 PrependInstructions(std::deque<MachineInstr *> &IBef,
 442                     MachineCodeForBasicBlock& MIVec,
 443                     MachineCodeForBasicBlock::iterator& MII,
 444                     const std::string& msg)
 445 {
 446   if (!IBef.empty())
 447     {
 448       MachineInstr* OrigMI = *MII;
 449       std::deque<MachineInstr *>::iterator AdIt;
 450       for (AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt)
 451         {
 452           if (DEBUG_RA) {
 453             if (OrigMI) cerr << "For MInst: " << *OrigMI;
 454             cerr << msg << " PREPENDed instr: " << **AdIt << "\n";
 455           }
 456           MII = MIVec.insert(MII, *AdIt);
 457           ++MII;
 458         }
 459     }
 460 }
 461
 462 inline void
 463 AppendInstructions(std::deque<MachineInstr *> &IAft,
 464                    MachineCodeForBasicBlock& MIVec,
 465                    MachineCodeForBasicBlock::iterator& MII,
 466                    const std::string& msg)
 467 {
 468   if (!IAft.empty())
 469     {
 470       MachineInstr* OrigMI = *MII;
 471       std::deque<MachineInstr *>::iterator AdIt;
 472       for( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt )
 473         {
 474           if(DEBUG_RA) {
 475             if (OrigMI) cerr << "For MInst: " << *OrigMI;
 476             cerr << msg << " APPENDed instr: "  << **AdIt << "\n";
 477           }
 478           ++MII;    // insert before the next instruction
 479           MII = MIVec.insert(MII, *AdIt);
 480         }
 481     }
 482 }
 483
 484
 485 void PhyRegAlloc::updateMachineCode()
 486 {
 487   const BasicBlock* entryBB = Meth->getEntryNode();
 488   if (entryBB) {
 489     MachineCodeForBasicBlock& MIVec = entryBB->getMachineInstrVec();
 490     MachineCodeForBasicBlock::iterator MII = MIVec.begin();
 491
 492     // Insert any instructions needed at method entry
 493     PrependInstructions(AddedInstrAtEntry.InstrnsBefore, MIVec, MII,
 494                         "At function entry: \n");
 495     assert(AddedInstrAtEntry.InstrnsAfter.empty() &&
 496            "InstrsAfter should be unnecessary since we are just inserting at "
 497            "the function entry point here.");
 498   }
 499
 500   for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
 501        BBI != BBE; ++BBI) {
 502
 503     // iterate over all the machine instructions in BB
 504     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 505     for(MachineCodeForBasicBlock::iterator MII = MIVec.begin();
 506         MII != MIVec.end(); ++MII) {
 507
 508       MachineInstr *MInst = *MII;
 509
 510       unsigned Opcode =  MInst->getOpCode();
 511
 512       // do not process Phis
 513       if (TM.getInstrInfo().isDummyPhiInstr(Opcode))
 514         continue;
 515
 516       // Now insert speical instructions (if necessary) for call/return
 517       // instructions.
 518       //
 519       if (TM.getInstrInfo().isCall(Opcode) ||
 520           TM.getInstrInfo().isReturn(Opcode)) {
 521
 522         AddedInstrns &AI = AddedInstrMap[MInst];
 523
 524         // Tmp stack poistions are needed by some calls that have spilled args
 525         // So reset it before we call each such method
 526         //
 527         mcInfo.popAllTempValues(TM);
 528
 529         if (TM.getInstrInfo().isCall(Opcode))
 530           MRI.colorCallArgs(MInst, LRI, &AI, *this, *BBI);
 531         else if (TM.getInstrInfo().isReturn(Opcode))
 532           MRI.colorRetValue(MInst, LRI, &AI);
 533       }
 534
 535
 536       /* -- Using above code instead of this
 537
 538       // if this machine instr is call, insert caller saving code
 539
 540       if( (TM.getInstrInfo()).isCall( MInst->getOpCode()) )
 541         MRI.insertCallerSavingCode(MInst,  *BBI, *this );
 542
 543       */
 544
 545
 546       // reset the stack offset for temporary variables since we may
 547       // need that to spill
 548       // mcInfo.popAllTempValues(TM);
 549       // TODO ** : do later
 550
 551       //for(MachineInstr::val_const_op_iterator OpI(MInst);!OpI.done();++OpI) {
 552
 553
 554       // Now replace set the registers for operands in the machine instruction
 555       //
 556       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 557
 558         MachineOperand& Op = MInst->getOperand(OpNum);
 559
 560         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 561             Op.getOperandType() ==  MachineOperand::MO_CCRegister) {
 562
 563           const Value *const Val =  Op.getVRegValue();
 564
 565           // delete this condition checking later (must assert if Val is null)
 566           if( !Val) {
 567             if (DEBUG_RA)
 568               cerr << "Warning: NULL Value found for operand\n";
 569             continue;
 570           }
 571           assert( Val && "Value is NULL");
 572
 573           LiveRange *const LR = LRI.getLiveRangeForValue(Val);
 574
 575           if ( !LR ) {
 576
 577             // nothing to worry if it's a const or a label
 578
 579             if (DEBUG_RA) {
 580               cerr << "*NO LR for operand : " << Op ;
 581               cerr << " [reg:" <<  Op.getAllocatedRegNum() << "]";
 582               cerr << " in inst:\t" << *MInst << "\n";
 583             }
 584
 585             // if register is not allocated, mark register as invalid
 586             if( Op.getAllocatedRegNum() == -1)
 587               Op.setRegForValue( MRI.getInvalidRegNum());
 588
 589
 590             continue;
 591           }
 592
 593           unsigned RCID = (LR->getRegClass())->getID();
 594
 595           if( LR->hasColor() ) {
 596             Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) );
 597           }
 598           else {
 599
 600             // LR did NOT receive a color (register). Now, insert spill code
 601             // for spilled opeands in this machine instruction
 602
 603             //assert(0 && "LR must be spilled");
 604             insertCode4SpilledLR(LR, MInst, *BBI, OpNum );
 605
 606           }
 607         }
 608
 609       } // for each operand
 610
 611
 612       // Now add instructions that the register allocator inserts before/after
 613       // this machine instructions (done only for calls/rets/incoming args)
 614       // We do this here, to ensure that spill for an instruction is inserted
 615       // closest as possible to an instruction (see above insertCode4Spill...)
 616       //
 617       // If there are instructions to be added, *before* this machine
 618       // instruction, add them now.
 619       //
 620       if(AddedInstrMap.count(MInst)) {
 621         PrependInstructions(AddedInstrMap[MInst].InstrnsBefore, MIVec, MII,"");
 622       }
 623
 624       // If there are instructions to be added *after* this machine
 625       // instruction, add them now
 626       //
 627       if (!AddedInstrMap[MInst].InstrnsAfter.empty()) {
 628
 629         // if there are delay slots for this instruction, the instructions
 630         // added after it must really go after the delayed instruction(s)
 631         // So, we move the InstrAfter of the current instruction to the
 632         // corresponding delayed instruction
 633
 634         unsigned delay;
 635         if ((delay=TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) >0){
 636           move2DelayedInstr(MInst,  *(MII+delay) );
 637
 638           if(DEBUG_RA)  cerr<< "\nMoved an added instr after the delay slot";
 639         }
 640
 641         else {
 642           // Here we can add the "instructions after" to the current
 643           // instruction since there are no delay slots for this instruction
 644           AppendInstructions(AddedInstrMap[MInst].InstrnsAfter, MIVec, MII,"");
 645         }  // if not delay
 646
 647       }
 648
 649     } // for each machine instruction
 650   }
 651 }
 652
 653
 654
 655 //----------------------------------------------------------------------------
 656 // This method inserts spill code for AN operand whose LR was spilled.
 657 // This method may be called several times for a single machine instruction
 658 // if it contains many spilled operands. Each time it is called, it finds
 659 // a register which is not live at that instruction and also which is not
 660 // used by other spilled operands of the same instruction. Then it uses
 661 // this register temporarily to accomodate the spilled value.
 662 //----------------------------------------------------------------------------
 663 void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR,
 664                                        MachineInstr *MInst,
 665                                        const BasicBlock *BB,
 666                                        const unsigned OpNum) {
 667
 668   assert(! TM.getInstrInfo().isCall(MInst->getOpCode()) &&
 669          (! TM.getInstrInfo().isReturn(MInst->getOpCode())) &&
 670          "Arg of a call/ret must be handled elsewhere");
 671
 672   MachineOperand& Op = MInst->getOperand(OpNum);
 673   bool isDef =  MInst->operandIsDefined(OpNum);
 674   unsigned RegType = MRI.getRegType( LR );
 675   int SpillOff = LR->getSpillOffFromFP();
 676   RegClass *RC = LR->getRegClass();
 677   const ValueSet &LVSetBef = LVI->getLiveVarSetBeforeMInst(MInst, BB);
 678
 679   mcInfo.pushTempValue(TM, MRI.getSpilledRegSize(RegType) );
 680
 681   MachineInstr *MIBef=NULL,  *AdIMid=NULL, *MIAft=NULL;
 682
 683   int TmpRegU = getUsableUniRegAtMI(RC, RegType, MInst,&LVSetBef, MIBef, MIAft);
 684
 685   // get the added instructions for this instruciton
 686   AddedInstrns &AI = AddedInstrMap[MInst];
 687
 688   if (!isDef) {
 689     // for a USE, we have to load the value of LR from stack to a TmpReg
 690     // and use the TmpReg as one operand of instruction
 691
 692     // actual loading instruction
 693     AdIMid = MRI.cpMem2RegMI(MRI.getFramePointer(), SpillOff, TmpRegU,RegType);
 694
 695     if(MIBef)
 696       AI.InstrnsBefore.push_back(MIBef);
 697
 698     AI.InstrnsBefore.push_back(AdIMid);
 699
 700     if(MIAft)
 701       AI.InstrnsAfter.push_front(MIAft);
 702
 703   } else {   // if this is a Def
 704     // for a DEF, we have to store the value produced by this instruction
 705     // on the stack position allocated for this LR
 706
 707     // actual storing instruction
 708     AdIMid = MRI.cpReg2MemMI(TmpRegU, MRI.getFramePointer(), SpillOff,RegType);
 709
 710     if (MIBef)
 711       AI.InstrnsBefore.push_back(MIBef);
 712
 713     AI.InstrnsAfter.push_front(AdIMid);
 714
 715     if (MIAft)
 716       AI.InstrnsAfter.push_front(MIAft);
 717
 718   }  // if !DEF
 719
 720   cerr << "\nFor Inst " << *MInst;
 721   cerr << " - SPILLED LR: "; printSet(*LR);
 722   cerr << "\n - Added Instructions:";
 723   if (MIBef) cerr <<  *MIBef;
 724   cerr <<  *AdIMid;
 725   if (MIAft) cerr <<  *MIAft;
 726
 727   Op.setRegForValue(TmpRegU);    // set the opearnd
 728 }
 729
 730
 731
 732 //----------------------------------------------------------------------------
 733 // We can use the following method to get a temporary register to be used
 734 // BEFORE any given machine instruction. If there is a register available,
 735 // this method will simply return that register and set MIBef = MIAft = NULL.
 736 // Otherwise, it will return a register and MIAft and MIBef will contain
 737 // two instructions used to free up this returned register.
 738 // Returned register number is the UNIFIED register number
 739 //----------------------------------------------------------------------------
 740
 741 int PhyRegAlloc::getUsableUniRegAtMI(RegClass *RC,
 742                                   const int RegType,
 743                                   const MachineInstr *MInst,
 744                                   const ValueSet *LVSetBef,
 745                                   MachineInstr *&MIBef,
 746                                   MachineInstr *&MIAft) {
 747
 748   int RegU =  getUnusedUniRegAtMI(RC, MInst, LVSetBef);
 749
 750
 751   if( RegU != -1) {
 752     // we found an unused register, so we can simply use it
 753     MIBef = MIAft = NULL;
 754   }
 755   else {
 756     // we couldn't find an unused register. Generate code to free up a reg by
 757     // saving it on stack and restoring after the instruction
 758
 759     int TmpOff = mcInfo.pushTempValue(TM,  MRI.getSpilledRegSize(RegType) );
 760
 761     RegU = getUniRegNotUsedByThisInst(RC, MInst);
 762     MIBef = MRI.cpReg2MemMI(RegU, MRI.getFramePointer(), TmpOff, RegType );
 763     MIAft = MRI.cpMem2RegMI(MRI.getFramePointer(), TmpOff, RegU, RegType );
 764   }
 765
 766   return RegU;
 767 }
 768
 769 //----------------------------------------------------------------------------
 770 // This method is called to get a new unused register that can be used to
 771 // accomodate a spilled value.
 772 // This method may be called several times for a single machine instruction
 773 // if it contains many spilled operands. Each time it is called, it finds
 774 // a register which is not live at that instruction and also which is not
 775 // used by other spilled operands of the same instruction.
 776 // Return register number is relative to the register class. NOT
 777 // unified number
 778 //----------------------------------------------------------------------------
 779 int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC,
 780                                   const MachineInstr *MInst,
 781                                   const ValueSet *LVSetBef) {
 782
 783   unsigned NumAvailRegs =  RC->getNumOfAvailRegs();
 784
 785   bool *IsColorUsedArr = RC->getIsColorUsedArr();
 786
 787   for(unsigned i=0; i <  NumAvailRegs; i++)     // Reset array
 788       IsColorUsedArr[i] = false;
 789
 790   ValueSet::const_iterator LIt = LVSetBef->begin();
 791
 792   // for each live var in live variable set after machine inst
 793   for( ; LIt != LVSetBef->end(); ++LIt) {
 794
 795    //  get the live range corresponding to live var
 796     LiveRange *const LRofLV = LRI.getLiveRangeForValue(*LIt );
 797
 798     // LR can be null if it is a const since a const
 799     // doesn't have a dominating def - see Assumptions above
 800     if( LRofLV )
 801       if( LRofLV->hasColor() )
 802         IsColorUsedArr[ LRofLV->getColor() ] = true;
 803   }
 804
 805   // It is possible that one operand of this MInst was already spilled
 806   // and it received some register temporarily. If that's the case,
 807   // it is recorded in machine operand. We must skip such registers.
 808
 809   setRelRegsUsedByThisInst(RC, MInst);
 810
 811   unsigned c;                         // find first unused color
 812   for( c=0; c < NumAvailRegs; c++)
 813      if( ! IsColorUsedArr[ c ] ) break;
 814
 815   if(c < NumAvailRegs)
 816     return  MRI.getUnifiedRegNum(RC->getID(), c);
 817   else
 818     return -1;
 819
 820
 821 }
 822
 823
 824 //----------------------------------------------------------------------------
 825 // Get any other register in a register class, other than what is used
 826 // by operands of a machine instruction. Returns the unified reg number.
 827 //----------------------------------------------------------------------------
 828 int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC,
 829                                          const MachineInstr *MInst) {
 830
 831   bool *IsColorUsedArr = RC->getIsColorUsedArr();
 832   unsigned NumAvailRegs =  RC->getNumOfAvailRegs();
 833
 834
 835   for(unsigned i=0; i < NumAvailRegs ; i++)   // Reset array
 836     IsColorUsedArr[i] = false;
 837
 838   setRelRegsUsedByThisInst(RC, MInst);
 839
 840   unsigned c;                         // find first unused color
 841   for( c=0; c <  RC->getNumOfAvailRegs(); c++)
 842      if( ! IsColorUsedArr[ c ] ) break;
 843
 844   if(c < NumAvailRegs)
 845     return  MRI.getUnifiedRegNum(RC->getID(), c);
 846   else
 847     assert( 0 && "FATAL: No free register could be found in reg class!!");
 848   return 0;
 849 }
 850
 851
 852 //----------------------------------------------------------------------------
 853 // This method modifies the IsColorUsedArr of the register class passed to it.
 854 // It sets the bits corresponding to the registers used by this machine
 855 // instructions. Both explicit and implicit operands are set.
 856 //----------------------------------------------------------------------------
 857 void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC,
 858                                        const MachineInstr *MInst ) {
 859
 860  bool *IsColorUsedArr = RC->getIsColorUsedArr();
 861
 862  for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 863
 864    const MachineOperand& Op = MInst->getOperand(OpNum);
 865
 866     if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 867         Op.getOperandType() ==  MachineOperand::MO_CCRegister ) {
 868
 869       const Value *const Val =  Op.getVRegValue();
 870
 871       if( Val )
 872         if( MRI.getRegClassIDOfValue(Val) == RC->getID() ) {
 873           int Reg;
 874           if( (Reg=Op.getAllocatedRegNum()) != -1) {
 875             IsColorUsedArr[ Reg ] = true;
 876           }
 877           else {
 878             // it is possilbe that this operand still is not marked with
 879             // a register but it has a LR and that received a color
 880
 881             LiveRange *LROfVal =  LRI.getLiveRangeForValue(Val);
 882             if( LROfVal)
 883               if( LROfVal->hasColor() )
 884                 IsColorUsedArr[ LROfVal->getColor() ] = true;
 885           }
 886
 887         } // if reg classes are the same
 888     }
 889     else if (Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
 890       IsColorUsedArr[ Op.getMachineRegNum() ] = true;
 891     }
 892  }
 893
 894  // If there are implicit references, mark them as well
 895
 896  for(unsigned z=0; z < MInst->getNumImplicitRefs(); z++) {
 897
 898    LiveRange *const LRofImpRef =
 899      LRI.getLiveRangeForValue( MInst->getImplicitRef(z)  );
 900
 901    if(LRofImpRef && LRofImpRef->hasColor())
 902      IsColorUsedArr[LRofImpRef->getColor()] = true;
 903  }
 904 }
 905
 906
 907
 908
 909
 910
 911
 912
 913 //----------------------------------------------------------------------------
 914 // If there are delay slots for an instruction, the instructions
 915 // added after it must really go after the delayed instruction(s).
 916 // So, we move the InstrAfter of that instruction to the
 917 // corresponding delayed instruction using the following method.
 918
 919 //----------------------------------------------------------------------------
 920 void PhyRegAlloc::move2DelayedInstr(const MachineInstr *OrigMI,
 921                                     const MachineInstr *DelayedMI) {
 922
 923   // "added after" instructions of the original instr
 924   std::deque<MachineInstr *> &OrigAft = AddedInstrMap[OrigMI].InstrnsAfter;
 925
 926   // "added instructions" of the delayed instr
 927   AddedInstrns &DelayAdI = AddedInstrMap[DelayedMI];
 928
 929   // "added after" instructions of the delayed instr
 930   std::deque<MachineInstr *> &DelayedAft = DelayAdI.InstrnsAfter;
 931
 932   // go thru all the "added after instructions" of the original instruction
 933   // and append them to the "addded after instructions" of the delayed
 934   // instructions
 935   DelayedAft.insert(DelayedAft.end(), OrigAft.begin(), OrigAft.end());
 936
 937   // empty the "added after instructions" of the original instruction
 938   OrigAft.clear();
 939 }
 940
 941 //----------------------------------------------------------------------------
 942 // This method prints the code with registers after register allocation is
 943 // complete.
 944 //----------------------------------------------------------------------------
 945 void PhyRegAlloc::printMachineCode()
 946 {
 947
 948   cerr << "\n;************** Function " << Meth->getName()
 949        << " *****************\n";
 950
 951   for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
 952        BBI != BBE; ++BBI) {
 953     cerr << "\n"; printLabel(*BBI); cerr << ": ";
 954
 955     // get the iterator for machine instructions
 956     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 957     MachineCodeForBasicBlock::iterator MII = MIVec.begin();
 958
 959     // iterate over all the machine instructions in BB
 960     for( ; MII != MIVec.end(); ++MII) {
 961       MachineInstr *const MInst = *MII;
 962
 963       cerr << "\n\t";
 964       cerr << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 965
 966       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 967         MachineOperand& Op = MInst->getOperand(OpNum);
 968
 969         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 970             Op.getOperandType() ==  MachineOperand::MO_CCRegister /*||
 971             Op.getOperandType() ==  MachineOperand::MO_PCRelativeDisp*/ ) {
 972
 973           const Value *const Val = Op.getVRegValue () ;
 974           // ****this code is temporary till NULL Values are fixed
 975           if( ! Val ) {
 976             cerr << "\t<*NULL*>";
 977             continue;
 978           }
 979
 980           // if a label or a constant
 981           if(isa<BasicBlock>(Val)) {
 982             cerr << "\t"; printLabel(   Op.getVRegValue () );
 983           } else {
 984             // else it must be a register value
 985             const int RegNum = Op.getAllocatedRegNum();
 986
 987             cerr << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
 988             if (Val->hasName() )
 989               cerr << "(" << Val->getName() << ")";
 990             else
 991               cerr << "(" << Val << ")";
 992
 993             if( Op.opIsDef() )
 994               cerr << "*";
 995
 996             const LiveRange *LROfVal = LRI.getLiveRangeForValue(Val);
 997             if( LROfVal )
 998               if( LROfVal->hasSpillOffset() )
 999                 cerr << "$";
1000           }
1001
1002         }
1003         else if(Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
1004           cerr << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
1005         }
1006
1007         else
1008           cerr << "\t" << Op;      // use dump field
1009       }
1010
1011
1012
1013       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
1014       if( NumOfImpRefs > 0) {
1015         cerr << "\tImplicit:";
1016
1017         for(unsigned z=0; z < NumOfImpRefs; z++)
1018           cerr << RAV(MInst->getImplicitRef(z)) << "\t";
1019       }
1020
1021     } // for all machine instructions
1022
1023     cerr << "\n";
1024
1025   } // for all BBs
1026
1027   cerr << "\n";
1028 }
1029
1030
1031 #if 0
1032
1033 //----------------------------------------------------------------------------
1034 //
1035 //----------------------------------------------------------------------------
1036
1037 void PhyRegAlloc::colorCallRetArgs()
1038 {
1039
1040   CallRetInstrListType &CallRetInstList = LRI.getCallRetInstrList();
1041   CallRetInstrListType::const_iterator It = CallRetInstList.begin();
1042
1043   for( ; It != CallRetInstList.end(); ++It ) {
1044
1045     const MachineInstr *const CRMI = *It;
1046     unsigned OpCode =  CRMI->getOpCode();
1047
1048     // get the added instructions for this Call/Ret instruciton
1049     AddedInstrns &AI = AddedInstrMap[CRMI];
1050
1051     // Tmp stack positions are needed by some calls that have spilled args
1052     // So reset it before we call each such method
1053     //mcInfo.popAllTempValues(TM);
1054
1055
1056     if (TM.getInstrInfo().isCall(OpCode))
1057       MRI.colorCallArgs(CRMI, LRI, &AI, *this);
1058     else if (TM.getInstrInfo().isReturn(OpCode))
1059       MRI.colorRetValue(CRMI, LRI, &AI);
1060     else
1061       assert(0 && "Non Call/Ret instrn in CallRetInstrList\n");
1062   }
1063 }
1064
1065 #endif
1066
1067 //----------------------------------------------------------------------------
1068
1069 //----------------------------------------------------------------------------
1070 void PhyRegAlloc::colorIncomingArgs()
1071 {
1072   const BasicBlock *const FirstBB = Meth->front();
1073   const MachineInstr *FirstMI = FirstBB->getMachineInstrVec().front();
1074   assert(FirstMI && "No machine instruction in entry BB");
1075
1076   MRI.colorMethodArgs(Meth, LRI, &AddedInstrAtEntry);
1077 }
1078
1079
1080 //----------------------------------------------------------------------------
1081 // Used to generate a label for a basic block
1082 //----------------------------------------------------------------------------
1083 void PhyRegAlloc::printLabel(const Value *const Val) {
1084   if (Val->hasName())
1085     cerr  << Val->getName();
1086   else
1087     cerr << "Label" <<  Val;
1088 }
1089
1090
1091 //----------------------------------------------------------------------------
1092 // This method calls setSugColorUsable method of each live range. This
1093 // will determine whether the suggested color of LR is  really usable.
1094 // A suggested color is not usable when the suggested color is volatile
1095 // AND when there are call interferences
1096 //----------------------------------------------------------------------------
1097
1098 void PhyRegAlloc::markUnusableSugColors()
1099 {
1100   if(DEBUG_RA ) cerr << "\nmarking unusable suggested colors ...\n";
1101
1102   // hash map iterator
1103   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
1104   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
1105
1106     for(; HMI != HMIEnd ; ++HMI ) {
1107       if (HMI->first) {
1108         LiveRange *L = HMI->second;      // get the LiveRange
1109         if (L) {
1110           if(L->hasSuggestedColor()) {
1111             int RCID = L->getRegClass()->getID();
1112             if( MRI.isRegVolatile( RCID,  L->getSuggestedColor()) &&
1113                 L->isCallInterference() )
1114               L->setSuggestedColorUsable( false );
1115             else
1116               L->setSuggestedColorUsable( true );
1117           }
1118         } // if L->hasSuggestedColor()
1119       }
1120     } // for all LR's in hash map
1121 }
1122
1123
1124
1125 //----------------------------------------------------------------------------
1126 // The following method will set the stack offsets of the live ranges that
1127 // are decided to be spillled. This must be called just after coloring the
1128 // LRs using the graph coloring algo. For each live range that is spilled,
1129 // this method allocate a new spill position on the stack.
1130 //----------------------------------------------------------------------------
1131
1132 void PhyRegAlloc::allocateStackSpace4SpilledLRs() {
1133   if (DEBUG_RA) cerr << "\nsetting LR stack offsets ...\n";
1134
1135   LiveRangeMapType::const_iterator HMI    = LRI.getLiveRangeMap()->begin();
1136   LiveRangeMapType::const_iterator HMIEnd = LRI.getLiveRangeMap()->end();
1137
1138   for( ; HMI != HMIEnd ; ++HMI) {
1139     if (HMI->first && HMI->second) {
1140       LiveRange *L = HMI->second;      // get the LiveRange
1141       if (!L->hasColor())   //  NOTE: ** allocating the size of long Type **
1142         L->setSpillOffFromFP(mcInfo.allocateSpilledValue(TM, Type::LongTy));
1143     }
1144   } // for all LR's in hash map
1145 }
1146
1147
1148
1149 //----------------------------------------------------------------------------
1150 // The entry pont to Register Allocation
1151 //----------------------------------------------------------------------------
1152
1153 void PhyRegAlloc::allocateRegisters()
1154 {
1155
1156   // make sure that we put all register classes into the RegClassList
1157   // before we call constructLiveRanges (now done in the constructor of
1158   // PhyRegAlloc class).
1159   //
1160   LRI.constructLiveRanges();            // create LR info
1161
1162   if (DEBUG_RA)
1163     LRI.printLiveRanges();
1164
1165   createIGNodeListsAndIGs();            // create IGNode list and IGs
1166
1167   buildInterferenceGraphs();            // build IGs in all reg classes
1168
1169
1170   if (DEBUG_RA) {
1171     // print all LRs in all reg classes
1172     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
1173       RegClassList[ rc ]->printIGNodeList();
1174
1175     // print IGs in all register classes
1176     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1177       RegClassList[ rc ]->printIG();
1178   }
1179
1180
1181   LRI.coalesceLRs();                    // coalesce all live ranges
1182
1183
1184   if( DEBUG_RA) {
1185     // print all LRs in all reg classes
1186     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
1187       RegClassList[ rc ]->printIGNodeList();
1188
1189     // print IGs in all register classes
1190     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1191       RegClassList[ rc ]->printIG();
1192   }
1193
1194
1195   // mark un-usable suggested color before graph coloring algorithm.
1196   // When this is done, the graph coloring algo will not reserve
1197   // suggested color unnecessarily - they can be used by another LR
1198   //
1199   markUnusableSugColors();
1200
1201   // color all register classes using the graph coloring algo
1202   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1203     RegClassList[ rc ]->colorAllRegs();
1204
1205   // Atter grpah coloring, if some LRs did not receive a color (i.e, spilled)
1206   // a poistion for such spilled LRs
1207   //
1208   allocateStackSpace4SpilledLRs();
1209
1210   mcInfo.popAllTempValues(TM);  // TODO **Check
1211
1212   // color incoming args - if the correct color was not received
1213   // insert code to copy to the correct register
1214   //
1215   colorIncomingArgs();
1216
1217   // Now update the machine code with register names and add any
1218   // additional code inserted by the register allocator to the instruction
1219   // stream
1220   //
1221   updateMachineCode();
1222
1223   if (DEBUG_RA) {
1224     MachineCodeForMethod::get(Meth).dump();
1225     printMachineCode();                   // only for DEBUGGING
1226   }
1227 }
1228
1229
1230