lib/CodeGen/RegAlloc/PhyRegAlloc.cpp

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