lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp

   1 #include "llvm/CodeGen/PhyRegAlloc.h"
   2
   3 cl::Enum<RegAllocDebugLevel_t> DEBUG_RA("dregalloc", cl::NoFlags,
   4   "enable register allocation debugging information",
   5   clEnumValN(RA_DEBUG_None   , "n", "disable debug output"),
   6   clEnumValN(RA_DEBUG_Normal , "y", "enable debug output"),
   7   clEnumValN(RA_DEBUG_Verbose, "v", "enable extra debug output"), 0);
   8
   9
  10 //----------------------------------------------------------------------------
  11 // Constructor: Init local composite objects and create register classes.
  12 //----------------------------------------------------------------------------
  13 PhyRegAlloc::PhyRegAlloc(const Method *const M,
  14                          const TargetMachine& tm,
  15                          MethodLiveVarInfo *const Lvi)
  16                         : RegClassList(),
  17                           Meth(M), TM(tm), LVI(Lvi), LRI(M, tm, RegClassList),
  18                           MRI( tm.getRegInfo() ),
  19                           NumOfRegClasses(MRI.getNumOfRegClasses()),
  20                           AddedInstrMap()
  21
  22 {
  23   // **TODO: use an actual reserved color list
  24   ReservedColorListType *RCL = new ReservedColorListType();
  25
  26   // create each RegisterClass and put in RegClassList
  27   for( unsigned int rc=0; rc < NumOfRegClasses; rc++)
  28     RegClassList.push_back( new RegClass(M, MRI.getMachineRegClass(rc), RCL) );
  29
  30 }
  31
  32 //----------------------------------------------------------------------------
  33 // This method initally creates interference graphs (one in each reg class)
  34 // and IGNodeList (one in each IG). The actual nodes will be pushed later.
  35 //----------------------------------------------------------------------------
  36
  37 void PhyRegAlloc::createIGNodeListsAndIGs()
  38 {
  39   if(DEBUG_RA ) cout << "Creating LR lists ..." << endl;
  40
  41   // hash map iterator
  42   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
  43
  44   // hash map end
  45   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
  46
  47     for(  ; HMI != HMIEnd ; ++HMI ) {
  48
  49       if( (*HMI).first ) {
  50
  51         LiveRange *L = (*HMI).second;      // get the LiveRange
  52
  53         if( !L) {
  54           if( DEBUG_RA) {
  55             cout << "\n*?!?Warning: Null liver range found for: ";
  56             printValue( (*HMI).first) ; cout << endl;
  57           }
  58           continue;
  59         }
  60                                         // if the Value * is not null, and LR
  61                                         // is not yet written to the IGNodeList
  62        if( !(L->getUserIGNode())  ) {
  63
  64          RegClass *const RC =           // RegClass of first value in the LR
  65            //RegClassList [MRI.getRegClassIDOfValue(*(L->begin()))];
  66            RegClassList[ L->getRegClass()->getID() ];
  67
  68          RC-> addLRToIG( L );           // add this LR to an IG
  69        }
  70     }
  71   }
  72
  73                                         // init RegClassList
  74   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
  75     RegClassList[ rc ]->createInterferenceGraph();
  76
  77   if( DEBUG_RA)
  78     cout << "LRLists Created!" << endl;
  79 }
  80
  81
  82
  83 //----------------------------------------------------------------------------
  84 // This method will add all interferences at for a given instruction.
  85 // Interence occurs only if the LR of Def (Inst or Arg) is of the same reg
  86 // class as that of live var. The live var passed to this function is the
  87 // LVset AFTER the instruction
  88 //----------------------------------------------------------------------------
  89
  90 void PhyRegAlloc::addInterference(const Value *const Def,
  91                                   const LiveVarSet *const LVSet,
  92                                   const bool isCallInst) {
  93
  94   LiveVarSet::const_iterator LIt = LVSet->begin();
  95
  96   // get the live range of instruction
  97   const LiveRange *const LROfDef = LRI.getLiveRangeForValue( Def );
  98
  99   IGNode *const IGNodeOfDef = LROfDef->getUserIGNode();
 100   assert( IGNodeOfDef );
 101
 102   RegClass *const RCOfDef = LROfDef->getRegClass();
 103
 104   // for each live var in live variable set
 105   for( ; LIt != LVSet->end(); ++LIt) {
 106
 107     if( DEBUG_RA > 1) {
 108       cout << "< Def="; printValue(Def);
 109       cout << ", Lvar=";  printValue( *LIt); cout  << "> ";
 110     }
 111
 112     //  get the live range corresponding to live var
 113     LiveRange *const LROfVar = LRI.getLiveRangeForValue(*LIt );
 114
 115     // LROfVar can be null if it is a const since a const
 116     // doesn't have a dominating def - see Assumptions above
 117     if( LROfVar)   {
 118
 119       if(LROfDef == LROfVar)            // do not set interf for same LR
 120         continue;
 121
 122       // if 2 reg classes are the same set interference
 123       if( RCOfDef == LROfVar->getRegClass() ){
 124         RCOfDef->setInterference( LROfDef, LROfVar);
 125
 126       }
 127
 128     else if(DEBUG_RA > 1)  {
 129       // we will not have LRs for values not explicitly allocated in the
 130       // instruction stream (e.g., constants)
 131       cout << " warning: no live range for " ;
 132       printValue( *LIt); cout << endl; }
 133
 134     }
 135
 136   }
 137
 138 }
 139
 140
 141 //----------------------------------------------------------------------------
 142 // For a call instruction, this method sets the CallInterference flag in
 143 // the LR of each variable live int the Live Variable Set live after the
 144 // call instruction (except the return value of the call instruction - since
 145 // the return value does not interfere with that call itself).
 146 //----------------------------------------------------------------------------
 147
 148 void PhyRegAlloc::setCallInterferences(const MachineInstr *MInst,
 149                                        const LiveVarSet *const LVSetAft )
 150 {
 151   // Now find the LR of the return value of the call
 152
 153
 154   // We do this because, we look at the LV set *after* the instruction
 155   // to determine, which LRs must be saved across calls. The return value
 156   // of the call is live in this set - but it does not interfere with call
 157   // (i.e., we can allocate a volatile register to the return value)
 158
 159   LiveRange *RetValLR = NULL;
 160
 161   const Value *RetVal = MRI.getCallInstRetVal( MInst );
 162
 163   if( RetVal ) {
 164     RetValLR = LRI.getLiveRangeForValue( RetVal );
 165     assert( RetValLR && "No LR for RetValue of call");
 166   }
 167
 168   if( DEBUG_RA)
 169     cout << "\n For call inst: " << *MInst;
 170
 171   LiveVarSet::const_iterator LIt = LVSetAft->begin();
 172
 173   // for each live var in live variable set after machine inst
 174   for( ; LIt != LVSetAft->end(); ++LIt) {
 175
 176    //  get the live range corresponding to live var
 177     LiveRange *const LR = LRI.getLiveRangeForValue(*LIt );
 178
 179     if( LR && DEBUG_RA) {
 180       cout << "\n\tLR Aft Call: ";
 181       LR->printSet();
 182     }
 183
 184
 185     // LR can be null if it is a const since a const
 186     // doesn't have a dominating def - see Assumptions above
 187     if( LR && (LR != RetValLR) )   {
 188       LR->setCallInterference();
 189       if( DEBUG_RA) {
 190         cout << "\n  ++Added call interf for LR: " ;
 191         LR->printSet();
 192       }
 193     }
 194
 195   }
 196
 197 }
 198
 199
 200 //----------------------------------------------------------------------------
 201 // This method will walk thru code and create interferences in the IG of
 202 // each RegClass.
 203 //----------------------------------------------------------------------------
 204
 205 void PhyRegAlloc::buildInterferenceGraphs()
 206 {
 207
 208   if(DEBUG_RA) cout << "Creating interference graphs ..." << endl;
 209
 210   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 211
 212   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 213
 214     // get the iterator for machine instructions
 215     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 216     MachineCodeForBasicBlock::const_iterator
 217       MInstIterator = MIVec.begin();
 218
 219     // iterate over all the machine instructions in BB
 220     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 221
 222       const MachineInstr *const MInst = *MInstIterator;
 223
 224       // get the LV set after the instruction
 225       const LiveVarSet *const LVSetAI =
 226         LVI->getLiveVarSetAfterMInst(MInst, *BBI);
 227
 228       const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
 229
 230       if( isCallInst ) {
 231         //cout << "\nFor call inst: " << *MInst;
 232
 233         // set the isCallInterference flag of each live range wich extends
 234         // accross this call instruction. This information is used by graph
 235         // coloring algo to avoid allocating volatile colors to live ranges
 236         // that span across calls (since they have to be saved/restored)
 237         setCallInterferences( MInst,  LVSetAI);
 238       }
 239
 240
 241       // iterate over  MI operands to find defs
 242       for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); ++OpI) {
 243
 244         if( OpI.isDef() ) {
 245           // create a new LR iff this operand is a def
 246           addInterference(*OpI, LVSetAI, isCallInst );
 247
 248         } //if this is a def
 249
 250       } // for all operands
 251
 252
 253       // Also add interference for any implicit definitions in a machine
 254       // instr (currently, only calls have this).
 255
 256       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 257       if(  NumOfImpRefs > 0 ) {
 258         for(unsigned z=0; z < NumOfImpRefs; z++)
 259           if( MInst->implicitRefIsDefined(z) )
 260             addInterference( MInst->getImplicitRef(z), LVSetAI, isCallInst );
 261       }
 262
 263     } // for all machine instructions in BB
 264
 265
 266 #if 0
 267
 268     // go thru LLVM instructions in the basic block and record all CALL
 269     // instructions and Return instructions in the CallInstrList
 270     // This is done because since there are no reverse pointers in machine
 271     // instructions to find the llvm instruction, when we encounter a call
 272     // or a return whose args must be specailly colored (e.g., %o's for args)
 273     BasicBlock::const_iterator InstIt = (*BBI)->begin();
 274
 275     for( ; InstIt != (*BBI)->end() ; ++ InstIt) {
 276       unsigned OpCode =  (*InstIt)->getOpcode();
 277
 278       if( OpCode == Instruction::Call )
 279         CallInstrList.push_back( *InstIt );
 280
 281       else if( OpCode == Instruction::Ret )
 282         RetInstrList.push_back( *InstIt );
 283     }
 284
 285 #endif
 286
 287
 288   } // for all BBs in method
 289
 290
 291   // add interferences for method arguments. Since there are no explict
 292   // defs in method for args, we have to add them manually
 293
 294   addInterferencesForArgs();            // add interference for method args
 295
 296   if( DEBUG_RA)
 297     cout << "Interference graphs calculted!" << endl;
 298
 299 }
 300
 301
 302
 303
 304 //----------------------------------------------------------------------------
 305 // This method will add interferences for incoming arguments to a method.
 306 //----------------------------------------------------------------------------
 307 void PhyRegAlloc::addInterferencesForArgs()
 308 {
 309                                               // get the InSet of root BB
 310   const LiveVarSet *const InSet = LVI->getInSetOfBB( Meth->front() );
 311
 312                                               // get the argument list
 313   const Method::ArgumentListType& ArgList = Meth->getArgumentList();
 314
 315                                               // get an iterator to arg list
 316   Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
 317
 318
 319   for( ; ArgIt != ArgList.end() ; ++ArgIt) {  // for each argument
 320     addInterference( *ArgIt, InSet, false );  // add interferences between
 321                                               // args and LVars at start
 322     if( DEBUG_RA > 1) {
 323        cout << " - %% adding interference for  argument ";
 324       printValue( (const Value *) *ArgIt); cout  << endl;
 325     }
 326   }
 327 }
 328
 329
 330
 331 //----------------------------------------------------------------------------
 332 // This method inserts caller saving/restoring instructons before/after
 333 // a call machine instruction.
 334 //----------------------------------------------------------------------------
 335
 336
 337 void PhyRegAlloc::insertCallerSavingCode(const MachineInstr *MInst,
 338                                          const BasicBlock *BB  )
 339 {
 340   // assert( (TM.getInstrInfo()).isCall( MInst->getOpCode() ) );
 341
 342   int StackOff = -8;  // ****TODO : Change
 343   hash_set<unsigned> PushedRegSet;
 344
 345   // Now find the LR of the return value of the call
 346   // The last *implicit operand* is the return value of a call
 347   // Insert it to to he PushedRegSet since we must not save that register
 348   // and restore it after the call.
 349   // We do this because, we look at the LV set *after* the instruction
 350   // to determine, which LRs must be saved across calls. The return value
 351   // of the call is live in this set - but we must not save/restore it.
 352
 353
 354   const Value *RetVal = MRI.getCallInstRetVal( MInst );
 355
 356   if( RetVal ) {
 357
 358     LiveRange *RetValLR = LRI.getLiveRangeForValue( RetVal );
 359     assert( RetValLR && "No LR for RetValue of call");
 360
 361     PushedRegSet.insert(
 362                  MRI.getUnifiedRegNum((RetValLR->getRegClass())->getID(),
 363                                       RetValLR->getColor() ) );
 364   }
 365
 366
 367   const LiveVarSet *LVSetAft =  LVI->getLiveVarSetAfterMInst(MInst, BB);
 368
 369   LiveVarSet::const_iterator LIt = LVSetAft->begin();
 370
 371   // for each live var in live variable set after machine inst
 372   for( ; LIt != LVSetAft->end(); ++LIt) {
 373
 374    //  get the live range corresponding to live var
 375     LiveRange *const LR = LRI.getLiveRangeForValue(*LIt );
 376
 377     // LR can be null if it is a const since a const
 378     // doesn't have a dominating def - see Assumptions above
 379     if( LR )   {
 380
 381       if( LR->hasColor() ) {
 382
 383         unsigned RCID = (LR->getRegClass())->getID();
 384         unsigned Color = LR->getColor();
 385
 386         if ( MRI.isRegVolatile(RCID, Color) ) {
 387
 388           // if the value is in both LV sets (i.e., live before and after
 389           // the call machine instruction)
 390
 391           unsigned Reg =   MRI.getUnifiedRegNum(RCID, Color);
 392
 393           if( PushedRegSet.find(Reg) == PushedRegSet.end() ) {
 394
 395             // if we haven't already pushed that register
 396
 397             unsigned RegType = MRI.getRegType( LR );
 398
 399             // Now get two instructions - to push on stack and pop from stack
 400             // and add them to InstrnsBefore and InstrnsAfter of the
 401             // call instruction
 402
 403             MachineInstr *AdIBef =
 404               MRI.cpReg2MemMI(Reg, MRI.getFramePointer(), StackOff, RegType );
 405
 406             MachineInstr *AdIAft =
 407               MRI.cpMem2RegMI(MRI.getFramePointer(), StackOff, Reg, RegType );
 408
 409             ((AddedInstrMap[MInst])->InstrnsBefore).push_front(AdIBef);
 410             ((AddedInstrMap[MInst])->InstrnsAfter).push_back(AdIAft);
 411
 412             PushedRegSet.insert( Reg );
 413             StackOff -= 8; // ****TODO: Correct ??????
 414
 415             if(DEBUG_RA) {
 416               cerr << "\nFor callee save call inst:" << *MInst;
 417               cerr << "\n  -inserted caller saving instrs:\n\t ";
 418               cerr << *AdIBef << "\n\t" << *AdIAft  ;
 419             }
 420           } // if not already pushed
 421
 422         } // if LR has a volatile color
 423
 424       } // if LR has color
 425
 426     } // if there is a LR for Var
 427
 428   } // for each value in the LV set after instruction
 429
 430 }
 431
 432
 433 //----------------------------------------------------------------------------
 434 // This method is called after register allocation is complete to set the
 435 // allocated reisters in the machine code. This code will add register numbers
 436 // to MachineOperands that contain a Value.
 437 //----------------------------------------------------------------------------
 438
 439 void PhyRegAlloc::updateMachineCode()
 440 {
 441
 442   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 443
 444   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 445
 446     // get the iterator for machine instructions
 447     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 448     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 449
 450     // iterate over all the machine instructions in BB
 451     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 452
 453       MachineInstr *MInst = *MInstIterator;
 454
 455       // if this machine instr is call, insert caller saving code
 456
 457       if( (TM.getInstrInfo()).isCall( MInst->getOpCode()) )
 458         insertCallerSavingCode(MInst,  *BBI );
 459
 460       // If there are instructions to be added, *before* this machine
 461       // instruction, add them now.
 462
 463       if( AddedInstrMap[ MInst ] ) {
 464
 465         deque<MachineInstr *> &IBef = (AddedInstrMap[MInst])->InstrnsBefore;
 466
 467         if( ! IBef.empty() ) {
 468
 469           deque<MachineInstr *>::iterator AdIt;
 470
 471           for( AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt ) {
 472
 473             if( DEBUG_RA)
 474               cerr << " *$* PREPENDed instr " << *AdIt << endl;
 475
 476             MInstIterator = MIVec.insert( MInstIterator, *AdIt );
 477             ++MInstIterator;
 478           }
 479
 480         }
 481
 482       }
 483
 484
 485
 486       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 487
 488       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 489
 490         MachineOperand& Op = MInst->getOperand(OpNum);
 491
 492         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 493             Op.getOperandType() ==  MachineOperand::MO_CCRegister) {
 494
 495           const Value *const Val =  Op.getVRegValue();
 496
 497           // delete this condition checking later (must assert if Val is null)
 498           if( !Val) {
 499             if (DEBUG_RA)
 500               cout << "Warning: NULL Value found for operand" << endl;
 501             continue;
 502           }
 503           assert( Val && "Value is NULL");
 504
 505           const LiveRange *const LR = LRI.getLiveRangeForValue(Val);
 506
 507           if ( !LR ) {
 508
 509             // nothing to worry if it's a const or a label
 510
 511             if (DEBUG_RA) {
 512               cout << "*NO LR for operand : " << Op ;
 513               cout << " [reg:" <<  Op.getAllocatedRegNum() << "]";
 514               cout << " in inst:\t" << *MInst << endl;
 515             }
 516
 517             // if register is not allocated, mark register as invalid
 518             if( Op.getAllocatedRegNum() == -1)
 519               Op.setRegForValue( MRI.getInvalidRegNum());
 520
 521 #if 0
 522             if(  ((Val->getType())->isLabelType()) ||
 523                  (Val->getValueType() == Value::ConstantVal)  )
 524               ;                         // do nothing
 525
 526             // The return address is not explicitly defined within a
 527             // method. So, it is not colored by usual algorithm. In that case
 528             // color it here.
 529
 530             //else if (TM.getInstrInfo().isCall(MInst->getOpCode()))
 531             //Op.setRegForValue( MRI.getCallAddressReg() );
 532
 533             //TM.getInstrInfo().isReturn(MInst->getOpCode())
 534             else if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ) {
 535               if (DEBUG_RA) cout << endl << "RETURN found" << endl;
 536               Op.setRegForValue( MRI.getReturnAddressReg() );
 537
 538             }
 539
 540             if (Val->getValueType() == Value::InstructionVal)
 541             {
 542               if( DEBUG_RA ) {
 543                 cout << "!Warning: No LiveRange for: ";
 544                 printValue( Val); cout << " Type: " << Val->getValueType();
 545                 cout << " RegVal=" <<  Op.getAllocatedRegNum() << endl;
 546               }
 547             }
 548
 549 #endif
 550
 551             continue;
 552           }
 553
 554           unsigned RCID = (LR->getRegClass())->getID();
 555
 556           Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) );
 557
 558           int RegNum = MRI.getUnifiedRegNum(RCID, LR->getColor());
 559
 560         }
 561
 562       } // for each operand
 563
 564
 565       // If there are instructions to be added *after* this machine
 566       // instruction, add them now
 567
 568       if( AddedInstrMap[ MInst ] &&
 569           ! (AddedInstrMap[ MInst ]->InstrnsAfter).empty() ) {
 570
 571         // if there are delay slots for this instruction, the instructions
 572         // added after it must really go after the delayed instruction(s)
 573         // So, we move the InstrAfter of the current instruction to the
 574         // corresponding delayed instruction
 575
 576         unsigned delay;
 577         if((delay=TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) >0){
 578           move2DelayedInstr(MInst,  *(MInstIterator+delay) );
 579
 580           if(DEBUG_RA)  cout<< "\nMoved an added instr after the delay slot";
 581         }
 582
 583         else {
 584
 585
 586           // Here we can add the "instructions after" to the current
 587           // instruction since there are no delay slots for this instruction
 588
 589           deque<MachineInstr *> &IAft = (AddedInstrMap[MInst])->InstrnsAfter;
 590
 591           if( ! IAft.empty() ) {
 592
 593             deque<MachineInstr *>::iterator AdIt;
 594
 595             ++MInstIterator;   // advance to the next instruction
 596
 597             for( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt ) {
 598
 599               if(DEBUG_RA)
 600                 cerr << " *#* APPENDed instr opcode: "  << *AdIt << endl;
 601
 602               MInstIterator = MIVec.insert( MInstIterator, *AdIt );
 603               ++MInstIterator;
 604             }
 605
 606             // MInsterator already points to the next instr. Since the
 607             // for loop also increments it, decrement it to point to the
 608             // instruction added last
 609             --MInstIterator;
 610
 611           }
 612
 613         }  // if not delay
 614
 615       }
 616
 617     } // for each machine instruction
 618   }
 619 }
 620
 621
 622 //----------------------------------------------------------------------------
 623 //
 624 // If there are delay slots for an instruction, the instructions
 625 // added after it must really go after the delayed instruction(s).
 626 // So, we move the InstrAfter of that instruction to the
 627 // corresponding delayed instruction using the following method.
 628
 629 //----------------------------------------------------------------------------
 630 void PhyRegAlloc:: move2DelayedInstr(const MachineInstr *OrigMI,
 631                                      const MachineInstr *DelayedMI) {
 632
 633
 634   // "added after" instructions of the original instr
 635   deque<MachineInstr *> &OrigAft = (AddedInstrMap[OrigMI])->InstrnsAfter;
 636
 637   // "added instructions" of the delayed instr
 638   AddedInstrns *DelayAdI = AddedInstrMap[DelayedMI];
 639
 640   if(! DelayAdI )  {                // create a new "added after" if necessary
 641     DelayAdI = new AddedInstrns();
 642     AddedInstrMap[DelayedMI] =  DelayAdI;
 643   }
 644
 645   // "added after" instructions of the delayed instr
 646   deque<MachineInstr *> &DelayedAft = DelayAdI->InstrnsAfter;
 647
 648   // go thru all the "added after instructions" of the original instruction
 649   // and append them to the "addded after instructions" of the delayed
 650   // instructions
 651
 652   deque<MachineInstr *>::iterator OrigAdIt;
 653
 654   for( OrigAdIt = OrigAft.begin(); OrigAdIt != OrigAft.end() ; ++OrigAdIt ) {
 655     DelayedAft.push_back( *OrigAdIt );
 656   }
 657
 658   // empty the "added after instructions" of the original instruction
 659   OrigAft.clear();
 660
 661 }
 662
 663 //----------------------------------------------------------------------------
 664 // This method prints the code with registers after register allocation is
 665 // complete.
 666 //----------------------------------------------------------------------------
 667 void PhyRegAlloc::printMachineCode()
 668 {
 669
 670   cout << endl << ";************** Method ";
 671   cout << Meth->getName() << " *****************" << endl;
 672
 673   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 674
 675   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 676
 677     cout << endl ; printLabel( *BBI); cout << ": ";
 678
 679     // get the iterator for machine instructions
 680     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 681     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 682
 683     // iterate over all the machine instructions in BB
 684     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 685
 686       MachineInstr *const MInst = *MInstIterator;
 687
 688
 689       cout << endl << "\t";
 690       cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 691
 692
 693       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 694
 695       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 696
 697         MachineOperand& Op = MInst->getOperand(OpNum);
 698
 699         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 700             Op.getOperandType() ==  MachineOperand::MO_CCRegister /*||
 701             Op.getOperandType() ==  MachineOperand::MO_PCRelativeDisp*/ ) {
 702
 703           const Value *const Val = Op.getVRegValue () ;
 704           // ****this code is temporary till NULL Values are fixed
 705           if( ! Val ) {
 706             cout << "\t<*NULL*>";
 707             continue;
 708           }
 709
 710           // if a label or a constant
 711           if( (Val->getValueType() == Value::BasicBlockVal)  ) {
 712
 713             cout << "\t"; printLabel(   Op.getVRegValue () );
 714           }
 715           else {
 716             // else it must be a register value
 717             const int RegNum = Op.getAllocatedRegNum();
 718
 719             cout << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
 720           }
 721
 722         }
 723         else if(Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
 724           cout << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
 725         }
 726
 727         else
 728           cout << "\t" << Op;      // use dump field
 729       }
 730
 731
 732
 733       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 734       if(  NumOfImpRefs > 0 ) {
 735
 736         cout << "\tImplicit:";
 737
 738         for(unsigned z=0; z < NumOfImpRefs; z++) {
 739           printValue(  MInst->getImplicitRef(z) );
 740           cout << "\t";
 741         }
 742
 743       }
 744
 745     } // for all machine instructions
 746
 747
 748     cout << endl;
 749
 750   } // for all BBs
 751
 752   cout << endl;
 753 }
 754
 755
 756 //----------------------------------------------------------------------------
 757 //
 758 //----------------------------------------------------------------------------
 759
 760 void PhyRegAlloc::colorCallRetArgs()
 761 {
 762
 763   CallRetInstrListType &CallRetInstList = LRI.getCallRetInstrList();
 764   CallRetInstrListType::const_iterator It = CallRetInstList.begin();
 765
 766   for( ; It != CallRetInstList.end(); ++It ) {
 767
 768     const MachineInstr *const CRMI = *It;
 769     unsigned OpCode =  CRMI->getOpCode();
 770
 771     // get the added instructions for this Call/Ret instruciton
 772     AddedInstrns *AI = AddedInstrMap[ CRMI ];
 773     if ( !AI ) {
 774       AI = new AddedInstrns();
 775       AddedInstrMap[ CRMI ] = AI;
 776     }
 777
 778     if( (TM.getInstrInfo()).isCall( OpCode ) )
 779       MRI.colorCallArgs( CRMI, LRI, AI );
 780
 781     else if (  (TM.getInstrInfo()).isReturn(OpCode) )
 782       MRI.colorRetValue( CRMI, LRI, AI );
 783
 784     else assert( 0 && "Non Call/Ret instrn in CallRetInstrList\n" );
 785
 786   }
 787
 788 }
 789
 790
 791
 792 //----------------------------------------------------------------------------
 793
 794 //----------------------------------------------------------------------------
 795 void PhyRegAlloc::colorIncomingArgs()
 796 {
 797   const BasicBlock *const FirstBB = Meth->front();
 798   const MachineInstr *FirstMI = *((FirstBB->getMachineInstrVec()).begin());
 799   assert( FirstMI && "No machine instruction in entry BB");
 800
 801   AddedInstrns *AI = AddedInstrMap[ FirstMI ];
 802   if ( !AI ) {
 803     AI = new AddedInstrns();
 804     AddedInstrMap[ FirstMI  ] = AI;
 805   }
 806
 807   MRI.colorMethodArgs(Meth, LRI, AI );
 808 }
 809
 810
 811 //----------------------------------------------------------------------------
 812 // Used to generate a label for a basic block
 813 //----------------------------------------------------------------------------
 814 void PhyRegAlloc::printLabel(const Value *const Val)
 815 {
 816   if( Val->hasName() )
 817     cout  << Val->getName();
 818   else
 819     cout << "Label" <<  Val;
 820 }
 821
 822
 823 //----------------------------------------------------------------------------
 824 // This method calls setSugColorUsable method of each live range. This
 825 // will determine whether the suggested color of LR is  really usable.
 826 // A suggested color is not usable when the suggested color is volatile
 827 // AND when there are call interferences
 828 //----------------------------------------------------------------------------
 829
 830 void PhyRegAlloc::markUnusableSugColors()
 831 {
 832   if(DEBUG_RA ) cout << "Creating LR lists ..." << endl;
 833
 834   // hash map iterator
 835   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
 836   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
 837
 838     for(  ; HMI != HMIEnd ; ++HMI ) {
 839
 840       if( (*HMI).first ) {
 841
 842         LiveRange *L = (*HMI).second;      // get the LiveRange
 843
 844         if(L) {
 845           if( L->hasSuggestedColor() ) {
 846
 847             int RCID = (L->getRegClass())->getID();
 848             if( MRI.isRegVolatile( RCID,  L->getSuggestedColor()) &&
 849                 L->isCallInterference() )
 850               L->setSuggestedColorUsable( false );
 851             else
 852               L->setSuggestedColorUsable( true );
 853           }
 854         } // if L->hasSuggestedColor()
 855       }
 856     } // for all LR's in hash map
 857 }
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869 //----------------------------------------------------------------------------
 870 // The entry pont to Register Allocation
 871 //----------------------------------------------------------------------------
 872
 873 void PhyRegAlloc::allocateRegisters()
 874 {
 875
 876   // make sure that we put all register classes into the RegClassList
 877   // before we call constructLiveRanges (now done in the constructor of
 878   // PhyRegAlloc class).
 879
 880   constructLiveRanges();                // create LR info
 881
 882   if( DEBUG_RA )
 883     LRI.printLiveRanges();
 884
 885   createIGNodeListsAndIGs();            // create IGNode list and IGs
 886
 887   buildInterferenceGraphs();            // build IGs in all reg classes
 888
 889
 890   if( DEBUG_RA ) {
 891     // print all LRs in all reg classes
 892     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
 893       RegClassList[ rc ]->printIGNodeList();
 894
 895     // print IGs in all register classes
 896     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 897       RegClassList[ rc ]->printIG();
 898   }
 899
 900   LRI.coalesceLRs();                    // coalesce all live ranges
 901
 902   if( DEBUG_RA) {
 903     // print all LRs in all reg classes
 904     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
 905       RegClassList[ rc ]->printIGNodeList();
 906
 907     // print IGs in all register classes
 908     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 909       RegClassList[ rc ]->printIG();
 910   }
 911
 912
 913   // mark un-usable suggested color before graph coloring algorithm.
 914   // When this is done, the graph coloring algo will not reserve
 915   // suggested color unnecessarily - they can be used by another LR
 916   markUnusableSugColors();
 917
 918   // color all register classes using the graph coloring algo
 919   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 920     RegClassList[ rc ]->colorAllRegs();
 921
 922
 923   // color incoming args and call args
 924   colorIncomingArgs();
 925   colorCallRetArgs();
 926
 927
 928   updateMachineCode();
 929   if (DEBUG_RA) {
 930     Meth->getMachineCode().dump();
 931     printMachineCode();                   // only for DEBUGGING
 932   }
 933 }
 934
 935
 936
 937