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