lib/CodeGen/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       //the live range of this var interferes with this call
 129       if( isCallInst )
 130         LROfVar->addCallInterference( (const Instruction *const) Def );
 131
 132     }
 133     else if(DEBUG_RA > 1)  {
 134       // we will not have LRs for values not explicitly allocated in the
 135       // instruction stream (e.g., constants)
 136       cout << " warning: no live range for " ;
 137       printValue( *LIt); cout << endl; }
 138
 139   }
 140
 141 }
 142
 143 //----------------------------------------------------------------------------
 144 // This method will walk thru code and create interferences in the IG of
 145 // each RegClass.
 146 //----------------------------------------------------------------------------
 147
 148 void PhyRegAlloc::buildInterferenceGraphs()
 149 {
 150
 151   if(DEBUG_RA) cout << "Creating interference graphs ..." << endl;
 152
 153   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 154
 155   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 156
 157     // get the iterator for machine instructions
 158     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 159     MachineCodeForBasicBlock::const_iterator
 160       MInstIterator = MIVec.begin();
 161
 162     // iterate over all the machine instructions in BB
 163     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 164
 165       const MachineInstr *const MInst = *MInstIterator;
 166
 167       // get the LV set after the instruction
 168       const LiveVarSet *const LVSetAI =
 169         LVI->getLiveVarSetAfterMInst(MInst, *BBI);
 170
 171       const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
 172
 173       // iterate over  MI operands to find defs
 174       for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); ++OpI) {
 175
 176         if( OpI.isDef() ) {
 177           // create a new LR iff this operand is a def
 178           addInterference(*OpI, LVSetAI, isCallInst );
 179
 180         } //if this is a def
 181
 182       } // for all operands
 183
 184     } // for all machine instructions in BB
 185
 186
 187 #if 0
 188
 189     // go thru LLVM instructions in the basic block and record all CALL
 190     // instructions and Return instructions in the CallInstrList
 191     // This is done because since there are no reverse pointers in machine
 192     // instructions to find the llvm instruction, when we encounter a call
 193     // or a return whose args must be specailly colored (e.g., %o's for args)
 194     BasicBlock::const_iterator InstIt = (*BBI)->begin();
 195
 196     for( ; InstIt != (*BBI)->end() ; ++ InstIt) {
 197       unsigned OpCode =  (*InstIt)->getOpcode();
 198
 199       if( OpCode == Instruction::Call )
 200         CallInstrList.push_back( *InstIt );
 201
 202       else if( OpCode == Instruction::Ret )
 203         RetInstrList.push_back( *InstIt );
 204    }
 205
 206 #endif
 207
 208
 209   } // for all BBs in method
 210
 211
 212   // add interferences for method arguments. Since there are no explict
 213   // defs in method for args, we have to add them manually
 214
 215   addInterferencesForArgs();            // add interference for method args
 216
 217   if( DEBUG_RA)
 218     cout << "Interference graphs calculted!" << endl;
 219
 220 }
 221
 222
 223
 224
 225 //----------------------------------------------------------------------------
 226 // This method will add interferences for incoming arguments to a method.
 227 //----------------------------------------------------------------------------
 228 void PhyRegAlloc::addInterferencesForArgs()
 229 {
 230                                               // get the InSet of root BB
 231   const LiveVarSet *const InSet = LVI->getInSetOfBB( Meth->front() );
 232
 233                                               // get the argument list
 234   const Method::ArgumentListType& ArgList = Meth->getArgumentList();
 235
 236                                               // get an iterator to arg list
 237   Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
 238
 239
 240   for( ; ArgIt != ArgList.end() ; ++ArgIt) {  // for each argument
 241     addInterference( *ArgIt, InSet, false );  // add interferences between
 242                                               // args and LVars at start
 243     if( DEBUG_RA > 1) {
 244       cout << " - %% adding interference for  argument ";
 245       printValue( (const Value *) *ArgIt); cout  << endl;
 246     }
 247   }
 248 }
 249
 250
 251 //----------------------------------------------------------------------------
 252 // This method is called after register allocation is complete to set the
 253 // allocated reisters in the machine code. This code will add register numbers
 254 // to MachineOperands that contain a Value.
 255 //----------------------------------------------------------------------------
 256
 257 void PhyRegAlloc::updateMachineCode()
 258 {
 259
 260   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 261
 262   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 263
 264     // get the iterator for machine instructions
 265     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 266     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 267
 268     // iterate over all the machine instructions in BB
 269     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 270
 271       MachineInstr *MInst = *MInstIterator;
 272
 273
 274       // If there are instructions before to be added, add them now
 275       // ***TODO: Add InstrnsAfter as well
 276       if( AddedInstrMap[ MInst ] ) {
 277
 278         vector<MachineInstr *> &IBef =
 279           (AddedInstrMap[MInst])->InstrnsBefore;
 280
 281         if( ! IBef.empty() ) {
 282
 283           vector<MachineInstr *>::iterator AdIt;
 284
 285           for( AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt ) {
 286
 287             cout << "*ADDED instr opcode: ";
 288             cout << TargetInstrDescriptors[(*AdIt)->getOpCode()].opCodeString;
 289             cout << endl;
 290
 291             MInstIterator = MIVec.insert( MInstIterator, *AdIt );
 292             ++MInstIterator;
 293           }
 294
 295         }
 296
 297         // restart from the topmost instruction added
 298         //MInst = *MInstIterator;
 299
 300       }
 301
 302
 303
 304       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 305
 306       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 307
 308         MachineOperand& Op = MInst->getOperand(OpNum);
 309
 310         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 311             Op.getOperandType() ==  MachineOperand::MO_CCRegister) {
 312
 313           const Value *const Val =  Op.getVRegValue();
 314
 315           // delete this condition checking later (must assert if Val is null)
 316           if( !Val) {
 317             if (DEBUG_RA)
 318               cout << "Warning: NULL Value found for operand" << endl;
 319             continue;
 320           }
 321           assert( Val && "Value is NULL");
 322
 323           const LiveRange *const LR = LRI.getLiveRangeForValue(Val);
 324
 325           if ( !LR ) {
 326
 327             // nothing to worry if it's a const or a label
 328
 329             if (DEBUG_RA) {
 330               cout << "*NO LR for inst opcode: ";
 331               cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 332             }
 333
 334             Op.setRegForValue( 1000 ); // mark register as invalid
 335
 336 #if 0
 337             if(  ((Val->getType())->isLabelType()) ||
 338                  (Val->getValueType() == Value::ConstantVal)  )
 339               ;                         // do nothing
 340
 341             // The return address is not explicitly defined within a
 342             // method. So, it is not colored by usual algorithm. In that case
 343             // color it here.
 344
 345             //else if (TM.getInstrInfo().isCall(MInst->getOpCode()))
 346             //Op.setRegForValue( MRI.getCallAddressReg() );
 347
 348             //TM.getInstrInfo().isReturn(MInst->getOpCode())
 349             else if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ) {
 350               if (DEBUG_RA) cout << endl << "RETURN found" << endl;
 351               Op.setRegForValue( MRI.getReturnAddressReg() );
 352
 353             }
 354
 355             if (Val->getValueType() == Value::InstructionVal)
 356             {
 357               cout << "!Warning: No LiveRange for: ";
 358               printValue( Val); cout << " Type: " << Val->getValueType();
 359               cout << " RegVal=" <<  Op.getAllocatedRegNum() << endl;
 360             }
 361
 362 #endif
 363
 364             continue;
 365           }
 366
 367           unsigned RCID = (LR->getRegClass())->getID();
 368
 369           Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) );
 370
 371           int RegNum = MRI.getUnifiedRegNum(RCID, LR->getColor());
 372
 373         }
 374
 375       }
 376
 377     }
 378   }
 379 }
 380
 381
 382
 383
 384 //----------------------------------------------------------------------------
 385 // This method prints the code with registers after register allocation is
 386 // complete.
 387 //----------------------------------------------------------------------------
 388 void PhyRegAlloc::printMachineCode()
 389 {
 390
 391   cout << endl << ";************** Method ";
 392   cout << Meth->getName() << " *****************" << endl;
 393
 394   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 395
 396   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 397
 398     cout << endl ; printLabel( *BBI); cout << ": ";
 399
 400     // get the iterator for machine instructions
 401     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 402     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 403
 404     // iterate over all the machine instructions in BB
 405     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 406
 407       MachineInstr *const MInst = *MInstIterator;
 408
 409
 410       cout << endl << "\t";
 411       cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 412
 413
 414       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 415
 416       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 417
 418         MachineOperand& Op = MInst->getOperand(OpNum);
 419
 420         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 421             Op.getOperandType() ==  MachineOperand::MO_CCRegister ||
 422             Op.getOperandType() ==  MachineOperand::MO_PCRelativeDisp ) {
 423
 424           const Value *const Val = Op.getVRegValue () ;
 425           // ****this code is temporary till NULL Values are fixed
 426           if( ! Val ) {
 427             cout << "\t<*NULL*>";
 428             continue;
 429           }
 430
 431           // if a label or a constant
 432           if( (Val->getValueType() == Value::BasicBlockVal)  ) {
 433
 434             cout << "\t"; printLabel(   Op.getVRegValue () );
 435           }
 436           else {
 437             // else it must be a register value
 438             const int RegNum = Op.getAllocatedRegNum();
 439
 440             //if( RegNum != 1000)
 441
 442               cout << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
 443             // else cout << "\t<*NoReg*>";
 444
 445           }
 446
 447         }
 448         else if(Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
 449           cout << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
 450         }
 451
 452         else
 453           cout << "\t" << Op;      // use dump field
 454       }
 455
 456     }
 457
 458     cout << endl;
 459
 460   }
 461
 462   cout << endl;
 463 }
 464
 465
 466 //----------------------------------------------------------------------------
 467 //
 468 //----------------------------------------------------------------------------
 469
 470 void PhyRegAlloc::colorCallRetArgs()
 471 {
 472
 473   CallRetInstrListType &CallRetInstList = LRI.getCallRetInstrList();
 474   CallRetInstrListType::const_iterator It = CallRetInstList.begin();
 475
 476   for( ; It != CallRetInstList.end(); ++It ) {
 477
 478     const Instruction *const CallRetI = *It;
 479     unsigned OpCode =  (CallRetI)->getOpcode();
 480
 481     const MachineInstr *CRMI = *((CallRetI->getMachineInstrVec()).begin());
 482
 483
 484     assert( (TM.getInstrInfo().isReturn(CRMI->getOpCode()) ||
 485              TM.getInstrInfo().isCall(CRMI->getOpCode()) )
 486             && "First Machine Instruction is not a Call/Retrunr" );
 487
 488     // get the added instructions for this Call/Ret instruciton
 489     AddedInstrns *AI = AddedInstrMap[ CRMI ];
 490     if ( !AI ) {
 491       AI = new AddedInstrns();
 492       AddedInstrMap[ CRMI ] = AI;
 493     }
 494
 495     if( (OpCode == Instruction::Call) )
 496         MRI.colorCallArgs( (CallInst *) CallRetI, LRI, AI );
 497
 498
 499     else if (OpCode == Instruction::Ret )
 500       MRI.colorRetValue( (ReturnInst *) CallRetI, LRI, AI       );
 501
 502
 503     else assert( 0 && "Non Call/Ret instrn in CallRetInstrList\n" );
 504
 505   }
 506
 507 }
 508
 509 //----------------------------------------------------------------------------
 510
 511 //----------------------------------------------------------------------------
 512 void PhyRegAlloc::colorIncomingArgs()
 513 {
 514   const BasicBlock *const FirstBB = Meth->front();
 515   const MachineInstr *FirstMI = *((FirstBB->getMachineInstrVec()).begin());
 516   assert( FirstMI && "No machine instruction in entry BB");
 517
 518   AddedInstrns *AI = AddedInstrMap[ FirstMI ];
 519   if ( !AI ) {
 520     AI = new AddedInstrns();
 521     AddedInstrMap[ FirstMI  ] = AI;
 522   }
 523
 524   MRI.colorMethodArgs(Meth, LRI, AI );
 525 }
 526
 527
 528 //----------------------------------------------------------------------------
 529 // Used to generate a label for a basic block
 530 //----------------------------------------------------------------------------
 531 void PhyRegAlloc::printLabel(const Value *const Val)
 532 {
 533   if( Val->hasName() )
 534     cout  << Val->getName();
 535   else
 536     cout << "Label" <<  Val;
 537 }
 538
 539
 540 //----------------------------------------------------------------------------
 541 // The entry pont to Register Allocation
 542 //----------------------------------------------------------------------------
 543
 544 void PhyRegAlloc::allocateRegisters()
 545 {
 546
 547   // make sure that we put all register classes into the RegClassList
 548   // before we call constructLiveRanges (now done in the constructor of
 549   // PhyRegAlloc class).
 550
 551   constructLiveRanges();                // create LR info
 552
 553   if( DEBUG_RA )
 554     LRI.printLiveRanges();
 555
 556   createIGNodeListsAndIGs();            // create IGNode list and IGs
 557
 558   buildInterferenceGraphs();            // build IGs in all reg classes
 559
 560
 561   if( DEBUG_RA ) {
 562     // print all LRs in all reg classes
 563     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
 564       RegClassList[ rc ]->printIGNodeList();
 565
 566     // print IGs in all register classes
 567     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 568       RegClassList[ rc ]->printIG();
 569   }
 570
 571   LRI.coalesceLRs();                    // coalesce all live ranges
 572
 573   if( DEBUG_RA) {
 574     // print all LRs in all reg classes
 575     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
 576       RegClassList[ rc ]->printIGNodeList();
 577
 578     // print IGs in all register classes
 579     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 580       RegClassList[ rc ]->printIG();
 581   }
 582
 583   // color all register classes
 584   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 585     RegClassList[ rc ]->colorAllRegs();
 586
 587
 588   // color incoming args and call args
 589   colorIncomingArgs();
 590   colorCallRetArgs();
 591
 592
 593   updateMachineCode();
 594   if (DEBUG_RA) {
 595     // PrintMachineInstructions(Meth);
 596     printMachineCode();                   // only for DEBUGGING
 597   }
 598 }
 599
 600
 601
 602