lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp

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