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