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