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