lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp

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