lib/CodeGen/RegAlloc/PhyRegAlloc.cpp

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