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                           CallInstrList(),
  21                           RetInstrList(),
  22                           AddedInstrMap()
  23
  24 {
  25   // **TODO: use an actual reserved color list
  26   ReservedColorListType *RCL = new ReservedColorListType();
  27
  28   // create each RegisterClass and put in RegClassList
  29   for( unsigned int rc=0; rc < NumOfRegClasses; rc++)
  30     RegClassList.push_back( new RegClass(M, MRI.getMachineRegClass(rc), RCL) );
  31
  32 }
  33
  34 //----------------------------------------------------------------------------
  35 // This method initally creates interference graphs (one in each reg class)
  36 // and IGNodeList (one in each IG). The actual nodes will be pushed later.
  37 //----------------------------------------------------------------------------
  38
  39 void PhyRegAlloc::createIGNodeListsAndIGs()
  40 {
  41   if(DEBUG_RA ) cout << "Creating LR lists ..." << endl;
  42
  43   // hash map iterator
  44   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
  45
  46   // hash map end
  47   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
  48
  49     for(  ; HMI != HMIEnd ; ++HMI ) {
  50
  51      LiveRange *L = (*HMI).second;      // get the LiveRange
  52
  53      if( (*HMI).first ) {
  54                                         // if the Value * is not null, and LR
  55                                         // is not yet written to the IGNodeList
  56        if( !(L->getUserIGNode())  ) {
  57
  58          RegClass *const RC =           // RegClass of first value in the LR
  59            //RegClassList [MRI.getRegClassIDOfValue(*(L->begin()))];
  60            RegClassList[ L->getRegClass()->getID() ];
  61
  62          RC-> addLRToIG( L );           // add this LR to an IG
  63        }
  64     }
  65   }
  66
  67                                         // init RegClassList
  68   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
  69     RegClassList[ rc ]->createInterferenceGraph();
  70
  71   if( DEBUG_RA)
  72     cout << "LRLists Created!" << endl;
  73 }
  74
  75
  76
  77 //----------------------------------------------------------------------------
  78 // This method will add all interferences at for a given instruction.
  79 // Interence occurs only if the LR of Def (Inst or Arg) is of the same reg
  80 // class as that of live var. The live var passed to this function is the
  81 // LVset AFTER the instruction
  82 //----------------------------------------------------------------------------
  83
  84 void PhyRegAlloc::addInterference(const Value *const Def,
  85                                   const LiveVarSet *const LVSet,
  86                                   const bool isCallInst) {
  87
  88   LiveVarSet::const_iterator LIt = LVSet->begin();
  89
  90   // get the live range of instruction
  91   const LiveRange *const LROfDef = LRI.getLiveRangeForValue( Def );
  92
  93   IGNode *const IGNodeOfDef = LROfDef->getUserIGNode();
  94   assert( IGNodeOfDef );
  95
  96   RegClass *const RCOfDef = LROfDef->getRegClass();
  97
  98   // for each live var in live variable set
  99   for( ; LIt != LVSet->end(); ++LIt) {
 100
 101     if( DEBUG_RA > 1) {
 102       cout << "< Def="; printValue(Def);
 103       cout << ", Lvar=";  printValue( *LIt); cout  << "> ";
 104     }
 105
 106     //  get the live range corresponding to live var
 107     LiveRange *const LROfVar = LRI.getLiveRangeForValue(*LIt );
 108
 109     // LROfVar can be null if it is a const since a const
 110     // doesn't have a dominating def - see Assumptions above
 111     if( LROfVar)   {
 112
 113       if(LROfDef == LROfVar)            // do not set interf for same LR
 114         continue;
 115
 116       // if 2 reg classes are the same set interference
 117       if( RCOfDef == LROfVar->getRegClass() ){
 118         RCOfDef->setInterference( LROfDef, LROfVar);
 119
 120       }
 121
 122       //the live range of this var interferes with this call
 123       if( isCallInst )
 124         LROfVar->addCallInterference( (const Instruction *const) Def );
 125
 126     }
 127     else if(DEBUG_RA > 1)  {
 128       // we will not have LRs for values not explicitly allocated in the
 129       // instruction stream (e.g., constants)
 130       cout << " warning: no live range for " ;
 131       printValue( *LIt); cout << endl; }
 132
 133   }
 134
 135 }
 136
 137 //----------------------------------------------------------------------------
 138 // This method will walk thru code and create interferences in the IG of
 139 // each RegClass.
 140 //----------------------------------------------------------------------------
 141
 142 void PhyRegAlloc::buildInterferenceGraphs()
 143 {
 144
 145   if(DEBUG_RA) cout << "Creating interference graphs ..." << endl;
 146
 147   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 148
 149   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 150
 151     // get the iterator for machine instructions
 152     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 153     MachineCodeForBasicBlock::const_iterator
 154       MInstIterator = MIVec.begin();
 155
 156     // iterate over all the machine instructions in BB
 157     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 158
 159       const MachineInstr *const MInst = *MInstIterator;
 160
 161       // get the LV set after the instruction
 162       const LiveVarSet *const LVSetAI =
 163         LVI->getLiveVarSetAfterMInst(MInst, *BBI);
 164
 165       const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
 166
 167       // iterate over  MI operands to find defs
 168       for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); ++OpI) {
 169
 170         if( OpI.isDef() ) {
 171           // create a new LR iff this operand is a def
 172           addInterference(*OpI, LVSetAI, isCallInst );
 173
 174         } //if this is a def
 175
 176       } // for all operands
 177
 178     } // for all machine instructions in BB
 179
 180
 181     // go thru LLVM instructions in the basic block and record all CALL
 182     // instructions and Return instructions in the CallInstrList
 183     // This is done because since there are no reverse pointers in machine
 184     // instructions to find the llvm instruction, when we encounter a call
 185     // or a return whose args must be specailly colored (e.g., %o's for args)
 186     BasicBlock::const_iterator InstIt = (*BBI)->begin();
 187
 188     for( ; InstIt != (*BBI)->end() ; ++ InstIt) {
 189       unsigned OpCode =  (*InstIt)->getOpcode();
 190
 191       if( OpCode == Instruction::Call )
 192         CallInstrList.push_back( *InstIt );
 193
 194       else if( OpCode == Instruction::Ret )
 195         RetInstrList.push_back( *InstIt );
 196    }
 197
 198   } // for all BBs in method
 199
 200
 201   // add interferences for method arguments. Since there are no explict
 202   // defs in method for args, we have to add them manually
 203
 204   addInterferencesForArgs();            // add interference for method args
 205
 206   if( DEBUG_RA)
 207     cout << "Interference graphs calculted!" << endl;
 208
 209 }
 210
 211
 212
 213
 214 //----------------------------------------------------------------------------
 215 // This method will add interferences for incoming arguments to a method.
 216 //----------------------------------------------------------------------------
 217 void PhyRegAlloc::addInterferencesForArgs()
 218 {
 219                                               // get the InSet of root BB
 220   const LiveVarSet *const InSet = LVI->getInSetOfBB( Meth->front() );
 221
 222                                               // get the argument list
 223   const Method::ArgumentListType& ArgList = Meth->getArgumentList();
 224
 225                                               // get an iterator to arg list
 226   Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
 227
 228
 229   for( ; ArgIt != ArgList.end() ; ++ArgIt) {  // for each argument
 230     addInterference( *ArgIt, InSet, false );  // add interferences between
 231                                               // args and LVars at start
 232     if( DEBUG_RA > 1) {
 233       cout << " - %% adding interference for  argument ";
 234       printValue( (const Value *) *ArgIt); cout  << endl;
 235     }
 236   }
 237 }
 238
 239
 240 //----------------------------------------------------------------------------
 241 // This method is called after register allocation is complete to set the
 242 // allocated reisters in the machine code. This code will add register numbers
 243 // to MachineOperands that contain a Value.
 244 //----------------------------------------------------------------------------
 245
 246 void PhyRegAlloc::updateMachineCode()
 247 {
 248
 249   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 250
 251   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 252
 253     // get the iterator for machine instructions
 254     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 255     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 256
 257     // iterate over all the machine instructions in BB
 258     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 259
 260       MachineInstr *const MInst = *MInstIterator;
 261
 262       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 263
 264       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 265
 266         MachineOperand& Op = MInst->getOperand(OpNum);
 267
 268         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 269             Op.getOperandType() ==  MachineOperand::MO_CCRegister) {
 270
 271           const Value *const Val =  Op.getVRegValue();
 272
 273           // delete this condition checking later (must assert if Val is null)
 274           if( !Val) {
 275             if (DEBUG_RA)
 276               cout << "Warning: NULL Value found for operand" << endl;
 277             continue;
 278           }
 279           assert( Val && "Value is NULL");
 280
 281           const LiveRange *const LR = LRI.getLiveRangeForValue(Val);
 282
 283           if ( !LR ) {
 284
 285             // nothing to worry if it's a const or a label
 286
 287             if (DEBUG_RA) {
 288               cout << "*NO LR for inst opcode: ";
 289               cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 290             }
 291
 292             Op.setRegForValue( -1 );  // mark register as invalid
 293
 294             if(  ((Val->getType())->isLabelType()) ||
 295                  (Val->getValueType() == Value::ConstantVal)  )
 296               ;                         // do nothing
 297
 298             // The return address is not explicitly defined within a
 299             // method. So, it is not colored by usual algorithm. In that case
 300             // color it here.
 301
 302             //else if (TM.getInstrInfo().isCall(MInst->getOpCode()))
 303             //Op.setRegForValue( MRI.getCallAddressReg() );
 304
 305             //TM.getInstrInfo().isReturn(MInst->getOpCode())
 306             else if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ) {
 307               if (DEBUG_RA) cout << endl << "RETURN found" << endl;
 308               Op.setRegForValue( MRI.getReturnAddressReg() );
 309
 310             }
 311
 312             else
 313             {
 314               cout << "!Warning: No LiveRange for: ";
 315               printValue( Val); cout << " Type: " << Val->getValueType();
 316               cout << " RegVal=" <<  Op.getAllocatedRegNum() << endl;
 317             }
 318
 319             continue;
 320           }
 321
 322           unsigned RCID = (LR->getRegClass())->getID();
 323
 324           Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) );
 325
 326           int RegNum = MRI.getUnifiedRegNum(RCID, LR->getColor());
 327
 328         }
 329
 330       }
 331
 332     }
 333   }
 334 }
 335
 336
 337
 338
 339 //----------------------------------------------------------------------------
 340 // This method prints the code with registers after register allocation is
 341 // complete.
 342 //----------------------------------------------------------------------------
 343 void PhyRegAlloc::printMachineCode()
 344 {
 345
 346   cout << endl << ";************** Method ";
 347   cout << Meth->getName() << " *****************" << endl;
 348
 349   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 350
 351   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 352
 353     cout << endl ; printLabel( *BBI); cout << ": ";
 354
 355     // get the iterator for machine instructions
 356     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 357     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 358
 359     // iterate over all the machine instructions in BB
 360     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 361
 362       MachineInstr *const MInst = *MInstIterator;
 363
 364
 365       cout << endl << "\t";
 366       cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 367
 368
 369       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 370
 371       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 372
 373         MachineOperand& Op = MInst->getOperand(OpNum);
 374
 375         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 376             Op.getOperandType() ==  MachineOperand::MO_CCRegister ||
 377             Op.getOperandType() ==  MachineOperand::MO_PCRelativeDisp ) {
 378
 379
 380
 381           const Value *const Val = Op.getVRegValue () ;
 382           // ****this code is temporary till NULL Values are fixed
 383           if( ! Val ) {
 384             cout << "\t<*NULL*>";
 385             continue;
 386           }
 387
 388           // if a label or a constant
 389           if( (Val->getValueType() == Value::BasicBlockVal) ||
 390               (Val->getValueType() == Value::ConstantVal) ) {
 391
 392             cout << "\t"; printLabel(   Op.getVRegValue () );
 393           }
 394           else {
 395             // else it must be a register value
 396             const int RegNum = Op.getAllocatedRegNum();
 397
 398               cout << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
 399
 400           }
 401
 402         }
 403         else if(Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
 404           cout << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
 405         }
 406
 407         else
 408           cout << "\t" << Op;      // use dump field
 409       }
 410
 411     }
 412
 413     cout << endl;
 414
 415   }
 416
 417   cout << endl;
 418 }
 419
 420
 421
 422 //----------------------------------------------------------------------------
 423 // Used to generate a label for a basic block
 424 //----------------------------------------------------------------------------
 425 void PhyRegAlloc::printLabel(const Value *const Val)
 426 {
 427   if( Val->hasName() )
 428     cout  << Val->getName();
 429   else
 430     cout << "Label" <<  Val;
 431 }
 432
 433
 434 //----------------------------------------------------------------------------
 435 // The entry pont to Register Allocation
 436 //----------------------------------------------------------------------------
 437
 438 void PhyRegAlloc::allocateRegisters()
 439 {
 440   constructLiveRanges();                // create LR info
 441
 442   if( DEBUG_RA)
 443     LRI.printLiveRanges();
 444
 445   createIGNodeListsAndIGs();            // create IGNode list and IGs
 446
 447   buildInterferenceGraphs();            // build IGs in all reg classes
 448
 449
 450   if( DEBUG_RA) {
 451     // print all LRs in all reg classes
 452     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
 453       RegClassList[ rc ]->printIGNodeList();
 454
 455     // print IGs in all register classes
 456     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 457       RegClassList[ rc ]->printIG();
 458   }
 459
 460   LRI.coalesceLRs();                    // coalesce all live ranges
 461
 462   if( DEBUG_RA) {
 463     // print all LRs in all reg classes
 464     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
 465       RegClassList[ rc ]->printIGNodeList();
 466
 467     // print IGs in all register classes
 468     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 469       RegClassList[ rc ]->printIG();
 470   }
 471
 472
 473   // the following three calls must be made in that order since
 474   // coloring or definitions must come before their uses
 475   MRI.colorArgs(Meth, LRI);             // color method args
 476                                         // color call args of call instrns
 477   MRI.colorCallArgs(CallInstrList, LRI, AddedInstrMap);
 478                                         // color return args
 479   MRI.colorRetArg(CallInstrList, LRI, AddedInstrMap);
 480
 481
 482
 483                                         // color all register classes
 484   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 485     RegClassList[ rc ]->colorAllRegs();
 486
 487   updateMachineCode();
 488   if (DEBUG_RA) {
 489     PrintMachineInstructions(Meth);
 490     printMachineCode();                   // only for DEBUGGING
 491   }
 492 }
 493
 494
 495
 496