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