lib/Target/SparcV9/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()) || OpNum == 0) &&
 596          "Outgoing arg of a call must be handled elsewhere (func arg ok)");
 597   assert(! TM.getInstrInfo().isReturn(MInst->getOpCode()) &&
 598          "Return value of a ret must be handled elsewhere");
 599
 600   MachineOperand& Op = MInst->getOperand(OpNum);
 601   bool isDef =  MInst->operandIsDefined(OpNum);
 602   bool isDefAndUse =  MInst->operandIsDefinedAndUsed(OpNum);
 603   unsigned RegType = MRI.getRegType( LR );
 604   int SpillOff = LR->getSpillOffFromFP();
 605   RegClass *RC = LR->getRegClass();
 606   const ValueSet &LVSetBef = LVI->getLiveVarSetBeforeMInst(MInst, BB);
 607
 608   mcInfo.pushTempValue(TM, MRI.getSpilledRegSize(RegType) );
 609
 610   vector<MachineInstr*> MIBef, MIAft;
 611   vector<MachineInstr*> AdIMid;
 612
 613   // Choose a register to hold the spilled value.  This may insert code
 614   // before and after MInst to free up the value.  If so, this code should
 615   // be first and last in the spill sequence before/after MInst.
 616   int TmpRegU = getUsableUniRegAtMI(RegType, &LVSetBef, MInst, MIBef, MIAft);
 617
 618   // Set the operand first so that it this register does not get used
 619   // as a scratch register for later calls to getUsableUniRegAtMI below
 620   MInst->SetRegForOperand(OpNum, TmpRegU);
 621
 622   // get the added instructions for this instruction
 623   AddedInstrns &AI = AddedInstrMap[MInst];
 624
 625   // We may need a scratch register to copy the spilled value to/from memory.
 626   // This may itself have to insert code to free up a scratch register.
 627   // Any such code should go before (after) the spill code for a load (store).
 628   int scratchRegType = -1;
 629   int scratchReg = -1;
 630   if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
 631     {
 632       scratchReg = this->getUsableUniRegAtMI(scratchRegType, &LVSetBef,
 633                                              MInst, MIBef, MIAft);
 634       assert(scratchReg != MRI.getInvalidRegNum());
 635       MInst->getRegsUsed().insert(scratchReg);
 636     }
 637
 638   if (!isDef || isDefAndUse) {
 639     // for a USE, we have to load the value of LR from stack to a TmpReg
 640     // and use the TmpReg as one operand of instruction
 641
 642     // actual loading instruction(s)
 643     MRI.cpMem2RegMI(AdIMid, MRI.getFramePointer(), SpillOff, TmpRegU, RegType,
 644                     scratchReg);
 645
 646     // the actual load should be after the instructions to free up TmpRegU
 647     MIBef.insert(MIBef.end(), AdIMid.begin(), AdIMid.end());
 648     AdIMid.clear();
 649   }
 650
 651   if (isDef) {   // if this is a Def
 652     // for a DEF, we have to store the value produced by this instruction
 653     // on the stack position allocated for this LR
 654
 655     // actual storing instruction(s)
 656     MRI.cpReg2MemMI(AdIMid, TmpRegU, MRI.getFramePointer(), SpillOff, RegType,
 657                     scratchReg);
 658
 659     MIAft.insert(MIAft.begin(), AdIMid.begin(), AdIMid.end());
 660   }  // if !DEF
 661
 662   // Finally, insert the entire spill code sequences before/after MInst
 663   AI.InstrnsBefore.insert(AI.InstrnsBefore.end(), MIBef.begin(), MIBef.end());
 664   AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(), MIAft.begin(), MIAft.end());
 665
 666   if (DEBUG_RA) {
 667     cerr << "\nFor Inst:\n  " << *MInst;
 668     cerr << "SPILLED LR# " << LR->getUserIGNode()->getIndex();
 669     cerr << "; added Instructions:";
 670     for_each(MIBef.begin(), MIBef.end(), std::mem_fun(&MachineInstr::dump));
 671     for_each(MIAft.begin(), MIAft.end(), std::mem_fun(&MachineInstr::dump));
 672   }
 673 }
 674
 675
 676 //----------------------------------------------------------------------------
 677 // We can use the following method to get a temporary register to be used
 678 // BEFORE any given machine instruction. If there is a register available,
 679 // this method will simply return that register and set MIBef = MIAft = NULL.
 680 // Otherwise, it will return a register and MIAft and MIBef will contain
 681 // two instructions used to free up this returned register.
 682 // Returned register number is the UNIFIED register number
 683 //----------------------------------------------------------------------------
 684
 685 int PhyRegAlloc::getUsableUniRegAtMI(const int RegType,
 686                                      const ValueSet *LVSetBef,
 687                                      MachineInstr *MInst,
 688                                      std::vector<MachineInstr*>& MIBef,
 689                                      std::vector<MachineInstr*>& MIAft) {
 690
 691   RegClass* RC = this->getRegClassByID(MRI.getRegClassIDOfRegType(RegType));
 692
 693   int RegU =  getUnusedUniRegAtMI(RC, MInst, LVSetBef);
 694
 695   if (RegU == -1) {
 696     // we couldn't find an unused register. Generate code to free up a reg by
 697     // saving it on stack and restoring after the instruction
 698
 699     int TmpOff = mcInfo.pushTempValue(TM,  MRI.getSpilledRegSize(RegType) );
 700
 701     RegU = getUniRegNotUsedByThisInst(RC, MInst);
 702
 703     // Check if we need a scratch register to copy this register to memory.
 704     int scratchRegType = -1;
 705     if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
 706       {
 707         int scratchReg = this->getUsableUniRegAtMI(scratchRegType, LVSetBef,
 708                                                    MInst, MIBef, MIAft);
 709         assert(scratchReg != MRI.getInvalidRegNum());
 710
 711         // We may as well hold the value in the scratch register instead
 712         // of copying it to memory and back.  But we have to mark the
 713         // register as used by this instruction, so it does not get used
 714         // as a scratch reg. by another operand or anyone else.
 715         MInst->getRegsUsed().insert(scratchReg);
 716         MRI.cpReg2RegMI(MIBef, RegU, scratchReg, RegType);
 717         MRI.cpReg2RegMI(MIAft, scratchReg, RegU, RegType);
 718       }
 719     else
 720       { // the register can be copied directly to/from memory so do it.
 721         MRI.cpReg2MemMI(MIBef, RegU, MRI.getFramePointer(), TmpOff, RegType);
 722         MRI.cpMem2RegMI(MIAft, MRI.getFramePointer(), TmpOff, RegU, RegType);
 723       }
 724   }
 725
 726   return RegU;
 727 }
 728
 729 //----------------------------------------------------------------------------
 730 // This method is called to get a new unused register that can be used to
 731 // accomodate a spilled value.
 732 // This method may be called several times for a single machine instruction
 733 // if it contains many spilled operands. Each time it is called, it finds
 734 // a register which is not live at that instruction and also which is not
 735 // used by other spilled operands of the same instruction.
 736 // Return register number is relative to the register class. NOT
 737 // unified number
 738 //----------------------------------------------------------------------------
 739 int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC,
 740                                   const MachineInstr *MInst,
 741                                   const ValueSet *LVSetBef) {
 742
 743   unsigned NumAvailRegs =  RC->getNumOfAvailRegs();
 744
 745   std::vector<bool> &IsColorUsedArr = RC->getIsColorUsedArr();
 746
 747   for (unsigned i=0; i <  NumAvailRegs; i++)     // Reset array
 748       IsColorUsedArr[i] = false;
 749
 750   ValueSet::const_iterator LIt = LVSetBef->begin();
 751
 752   // for each live var in live variable set after machine inst
 753   for ( ; LIt != LVSetBef->end(); ++LIt) {
 754
 755    //  get the live range corresponding to live var
 756     LiveRange *const LRofLV = LRI.getLiveRangeForValue(*LIt );
 757
 758     // LR can be null if it is a const since a const
 759     // doesn't have a dominating def - see Assumptions above
 760     if (LRofLV && LRofLV->getRegClass() == RC && LRofLV->hasColor() )
 761       IsColorUsedArr[ LRofLV->getColor() ] = true;
 762   }
 763
 764   // It is possible that one operand of this MInst was already spilled
 765   // and it received some register temporarily. If that's the case,
 766   // it is recorded in machine operand. We must skip such registers.
 767
 768   setRelRegsUsedByThisInst(RC, MInst);
 769
 770   for (unsigned c=0; c < NumAvailRegs; c++)   // find first unused color
 771      if (!IsColorUsedArr[c])
 772        return MRI.getUnifiedRegNum(RC->getID(), c);
 773
 774   return -1;
 775 }
 776
 777
 778 //----------------------------------------------------------------------------
 779 // Get any other register in a register class, other than what is used
 780 // by operands of a machine instruction. Returns the unified reg number.
 781 //----------------------------------------------------------------------------
 782 int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC,
 783                                             const MachineInstr *MInst) {
 784
 785   vector<bool> &IsColorUsedArr = RC->getIsColorUsedArr();
 786   unsigned NumAvailRegs =  RC->getNumOfAvailRegs();
 787
 788   for (unsigned i=0; i < NumAvailRegs ; i++)   // Reset array
 789     IsColorUsedArr[i] = false;
 790
 791   setRelRegsUsedByThisInst(RC, MInst);
 792
 793   for (unsigned c=0; c < RC->getNumOfAvailRegs(); c++)// find first unused color
 794     if (!IsColorUsedArr[c])
 795       return  MRI.getUnifiedRegNum(RC->getID(), c);
 796
 797   assert(0 && "FATAL: No free register could be found in reg class!!");
 798   return 0;
 799 }
 800
 801
 802 //----------------------------------------------------------------------------
 803 // This method modifies the IsColorUsedArr of the register class passed to it.
 804 // It sets the bits corresponding to the registers used by this machine
 805 // instructions. Both explicit and implicit operands are set.
 806 //----------------------------------------------------------------------------
 807 void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC,
 808                                            const MachineInstr *MInst ) {
 809
 810   vector<bool> &IsColorUsedArr = RC->getIsColorUsedArr();
 811
 812   // Add the registers already marked as used by the instruction.
 813   // This should include any scratch registers that are used to save
 814   // values across the instruction (e.g., for saving state register values).
 815   const hash_set<int>& regsUsed = MInst->getRegsUsed();
 816   for (hash_set<int>::const_iterator SI=regsUsed.begin(), SE=regsUsed.end();
 817        SI != SE; ++SI)
 818     {
 819       unsigned classId = 0;
 820       int classRegNum = MRI.getClassRegNum(*SI, classId);
 821       if (RC->getID() == classId)
 822         {
 823           assert(classRegNum < (int) IsColorUsedArr.size() &&
 824                  "Illegal register number for this reg class?");
 825           IsColorUsedArr[classRegNum] = true;
 826         }
 827     }
 828
 829   // Now add registers allocated to the live ranges of values used in
 830   // the instruction.  These are not yet recorded in the instruction.
 831   for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum)
 832     {
 833       const MachineOperand& Op = MInst->getOperand(OpNum);
 834
 835       if (Op.getOperandType() == MachineOperand::MO_VirtualRegister ||
 836           Op.getOperandType() == MachineOperand::MO_CCRegister)
 837         if (const Value* Val = Op.getVRegValue())
 838           if (MRI.getRegClassIDOfValue(Val) == RC->getID())
 839             if (Op.getAllocatedRegNum() == -1)
 840               if (LiveRange *LROfVal = LRI.getLiveRangeForValue(Val))
 841                 if (LROfVal->hasColor() )
 842                   // this operand is in a LR that received a color
 843                   IsColorUsedArr[LROfVal->getColor()] = true;
 844     }
 845
 846   // If there are implicit references, mark their allocated regs as well
 847   //
 848   for (unsigned z=0; z < MInst->getNumImplicitRefs(); z++)
 849     if (const LiveRange*
 850         LRofImpRef = LRI.getLiveRangeForValue(MInst->getImplicitRef(z)))
 851       if (LRofImpRef->hasColor())
 852         // this implicit reference is in a LR that received a color
 853         IsColorUsedArr[LRofImpRef->getColor()] = true;
 854 }
 855
 856
 857 //----------------------------------------------------------------------------
 858 // If there are delay slots for an instruction, the instructions
 859 // added after it must really go after the delayed instruction(s).
 860 // So, we move the InstrAfter of that instruction to the
 861 // corresponding delayed instruction using the following method.
 862
 863 //----------------------------------------------------------------------------
 864 void PhyRegAlloc::move2DelayedInstr(const MachineInstr *OrigMI,
 865                                     const MachineInstr *DelayedMI) {
 866
 867   // "added after" instructions of the original instr
 868   std::vector<MachineInstr *> &OrigAft = AddedInstrMap[OrigMI].InstrnsAfter;
 869
 870   // "added instructions" of the delayed instr
 871   AddedInstrns &DelayAdI = AddedInstrMap[DelayedMI];
 872
 873   // "added after" instructions of the delayed instr
 874   std::vector<MachineInstr *> &DelayedAft = DelayAdI.InstrnsAfter;
 875
 876   // go thru all the "added after instructions" of the original instruction
 877   // and append them to the "addded after instructions" of the delayed
 878   // instructions
 879   DelayedAft.insert(DelayedAft.end(), OrigAft.begin(), OrigAft.end());
 880
 881   // empty the "added after instructions" of the original instruction
 882   OrigAft.clear();
 883 }
 884
 885 //----------------------------------------------------------------------------
 886 // This method prints the code with registers after register allocation is
 887 // complete.
 888 //----------------------------------------------------------------------------
 889 void PhyRegAlloc::printMachineCode()
 890 {
 891
 892   cerr << "\n;************** Function " << Meth->getName()
 893        << " *****************\n";
 894
 895   for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
 896        BBI != BBE; ++BBI) {
 897     cerr << "\n"; printLabel(BBI); cerr << ": ";
 898
 899     // get the iterator for machine instructions
 900     MachineCodeForBasicBlock& MIVec = MachineCodeForBasicBlock::get(BBI);
 901     MachineCodeForBasicBlock::iterator MII = MIVec.begin();
 902
 903     // iterate over all the machine instructions in BB
 904     for ( ; MII != MIVec.end(); ++MII) {
 905       MachineInstr *const MInst = *MII;
 906
 907       cerr << "\n\t";
 908       cerr << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 909
 910       for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 911         MachineOperand& Op = MInst->getOperand(OpNum);
 912
 913         if (Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 914             Op.getOperandType() ==  MachineOperand::MO_CCRegister /*||
 915             Op.getOperandType() ==  MachineOperand::MO_PCRelativeDisp*/ ) {
 916
 917           const Value *const Val = Op.getVRegValue () ;
 918           // ****this code is temporary till NULL Values are fixed
 919           if (! Val ) {
 920             cerr << "\t<*NULL*>";
 921             continue;
 922           }
 923
 924           // if a label or a constant
 925           if (isa<BasicBlock>(Val)) {
 926             cerr << "\t"; printLabel(   Op.getVRegValue () );
 927           } else {
 928             // else it must be a register value
 929             const int RegNum = Op.getAllocatedRegNum();
 930
 931             cerr << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
 932             if (Val->hasName() )
 933               cerr << "(" << Val->getName() << ")";
 934             else
 935               cerr << "(" << Val << ")";
 936
 937             if (Op.opIsDef() )
 938               cerr << "*";
 939
 940             const LiveRange *LROfVal = LRI.getLiveRangeForValue(Val);
 941             if (LROfVal )
 942               if (LROfVal->hasSpillOffset() )
 943                 cerr << "$";
 944           }
 945
 946         }
 947         else if (Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
 948           cerr << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
 949         }
 950
 951         else
 952           cerr << "\t" << Op;      // use dump field
 953       }
 954
 955
 956
 957       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 958       if (NumOfImpRefs > 0) {
 959         cerr << "\tImplicit:";
 960
 961         for (unsigned z=0; z < NumOfImpRefs; z++)
 962           cerr << RAV(MInst->getImplicitRef(z)) << "\t";
 963       }
 964
 965     } // for all machine instructions
 966
 967     cerr << "\n";
 968
 969   } // for all BBs
 970
 971   cerr << "\n";
 972 }
 973
 974
 975 //----------------------------------------------------------------------------
 976
 977 //----------------------------------------------------------------------------
 978 void PhyRegAlloc::colorIncomingArgs()
 979 {
 980   const BasicBlock &FirstBB = Meth->front();
 981   const MachineInstr *FirstMI = MachineCodeForBasicBlock::get(&FirstBB).front();
 982   assert(FirstMI && "No machine instruction in entry BB");
 983
 984   MRI.colorMethodArgs(Meth, LRI, &AddedInstrAtEntry);
 985 }
 986
 987
 988 //----------------------------------------------------------------------------
 989 // Used to generate a label for a basic block
 990 //----------------------------------------------------------------------------
 991 void PhyRegAlloc::printLabel(const Value *const Val) {
 992   if (Val->hasName())
 993     cerr  << Val->getName();
 994   else
 995     cerr << "Label" <<  Val;
 996 }
 997
 998
 999 //----------------------------------------------------------------------------
1000 // This method calls setSugColorUsable method of each live range. This
1001 // will determine whether the suggested color of LR is  really usable.
1002 // A suggested color is not usable when the suggested color is volatile
1003 // AND when there are call interferences
1004 //----------------------------------------------------------------------------
1005
1006 void PhyRegAlloc::markUnusableSugColors()
1007 {
1008   // hash map iterator
1009   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
1010   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
1011
1012     for (; HMI != HMIEnd ; ++HMI ) {
1013       if (HMI->first) {
1014         LiveRange *L = HMI->second;      // get the LiveRange
1015         if (L) {
1016           if (L->hasSuggestedColor()) {
1017             int RCID = L->getRegClass()->getID();
1018             if (MRI.isRegVolatile( RCID,  L->getSuggestedColor()) &&
1019                 L->isCallInterference() )
1020               L->setSuggestedColorUsable( false );
1021             else
1022               L->setSuggestedColorUsable( true );
1023           }
1024         } // if L->hasSuggestedColor()
1025       }
1026     } // for all LR's in hash map
1027 }
1028
1029
1030
1031 //----------------------------------------------------------------------------
1032 // The following method will set the stack offsets of the live ranges that
1033 // are decided to be spillled. This must be called just after coloring the
1034 // LRs using the graph coloring algo. For each live range that is spilled,
1035 // this method allocate a new spill position on the stack.
1036 //----------------------------------------------------------------------------
1037
1038 void PhyRegAlloc::allocateStackSpace4SpilledLRs() {
1039   if (DEBUG_RA) cerr << "\nSetting LR stack offsets for spills...\n";
1040
1041   LiveRangeMapType::const_iterator HMI    = LRI.getLiveRangeMap()->begin();
1042   LiveRangeMapType::const_iterator HMIEnd = LRI.getLiveRangeMap()->end();
1043
1044   for ( ; HMI != HMIEnd ; ++HMI) {
1045     if (HMI->first && HMI->second) {
1046       LiveRange *L = HMI->second;      // get the LiveRange
1047       if (!L->hasColor()) {   //  NOTE: ** allocating the size of long Type **
1048         int stackOffset = mcInfo.allocateSpilledValue(TM, Type::LongTy);
1049         L->setSpillOffFromFP(stackOffset);
1050         if (DEBUG_RA)
1051           cerr << "  LR# " << L->getUserIGNode()->getIndex()
1052                << ": stack-offset = " << stackOffset << "\n";
1053       }
1054     }
1055   } // for all LR's in hash map
1056 }
1057
1058
1059
1060 //----------------------------------------------------------------------------
1061 // The entry pont to Register Allocation
1062 //----------------------------------------------------------------------------
1063
1064 void PhyRegAlloc::allocateRegisters()
1065 {
1066
1067   // make sure that we put all register classes into the RegClassList
1068   // before we call constructLiveRanges (now done in the constructor of
1069   // PhyRegAlloc class).
1070   //
1071   LRI.constructLiveRanges();            // create LR info
1072
1073   if (DEBUG_RA >= RA_DEBUG_LiveRanges)
1074     LRI.printLiveRanges();
1075
1076   createIGNodeListsAndIGs();            // create IGNode list and IGs
1077
1078   buildInterferenceGraphs();            // build IGs in all reg classes
1079
1080
1081   if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
1082     // print all LRs in all reg classes
1083     for ( unsigned rc=0; rc < NumOfRegClasses  ; rc++)
1084       RegClassList[rc]->printIGNodeList();
1085
1086     // print IGs in all register classes
1087     for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
1088       RegClassList[rc]->printIG();
1089   }
1090
1091
1092   LRI.coalesceLRs();                    // coalesce all live ranges
1093
1094
1095   if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
1096     // print all LRs in all reg classes
1097     for ( unsigned rc=0; rc < NumOfRegClasses  ; rc++)
1098       RegClassList[ rc ]->printIGNodeList();
1099
1100     // print IGs in all register classes
1101     for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
1102       RegClassList[ rc ]->printIG();
1103   }
1104
1105
1106   // mark un-usable suggested color before graph coloring algorithm.
1107   // When this is done, the graph coloring algo will not reserve
1108   // suggested color unnecessarily - they can be used by another LR
1109   //
1110   markUnusableSugColors();
1111
1112   // color all register classes using the graph coloring algo
1113   for (unsigned rc=0; rc < NumOfRegClasses ; rc++)
1114     RegClassList[ rc ]->colorAllRegs();
1115
1116   // Atter grpah coloring, if some LRs did not receive a color (i.e, spilled)
1117   // a poistion for such spilled LRs
1118   //
1119   allocateStackSpace4SpilledLRs();
1120
1121   mcInfo.popAllTempValues(TM);  // TODO **Check
1122
1123   // color incoming args - if the correct color was not received
1124   // insert code to copy to the correct register
1125   //
1126   colorIncomingArgs();
1127
1128   // Now update the machine code with register names and add any
1129   // additional code inserted by the register allocator to the instruction
1130   // stream
1131   //
1132   updateMachineCode();
1133
1134   if (DEBUG_RA) {
1135     cerr << "\n**** Machine Code After Register Allocation:\n\n";
1136     MachineCodeForMethod::get(Meth).dump();
1137   }
1138 }
1139
1140
1141