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