lib/CodeGen/RegAlloc/PhyRegAlloc.cpp

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