lib/Target/SparcV9/RegAlloc/PhyRegAloc.cpp

   1 #include "llvm/CodeGen/PhyRegAlloc.h"
   2
   3 //----------------------------------------------------------------------------
   4 //
   5 //----------------------------------------------------------------------------
   6
   7
   8
   9 //----------------------------------------------------------------------------
  10 // Constructor: Init local composite objects and create register classes.
  11 //----------------------------------------------------------------------------
  12 PhyRegAlloc::PhyRegAlloc(const Method *const M,
  13                          const TargetMachine& tm,
  14                          MethodLiveVarInfo *const Lvi)
  15                         : RegClassList(),
  16                           Meth(M), TM(tm), LVI(Lvi), LRI(M, tm, RegClassList),
  17                           MRI( tm.getRegInfo() ),
  18                           NumOfRegClasses(MRI.getNumOfRegClasses()),
  19                           CallInstrList(),
  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      LiveRange *L = (*HMI).second;      // get the LiveRange
  50
  51      if( (*HMI).first ) {
  52                                         // if the Value * is not null, and LR
  53                                         // is not yet written to the IGNodeList
  54        if( !(L->getUserIGNode())  ) {
  55
  56          RegClass *const RC =           // RegClass of first value in the LR
  57            //RegClassList [MRI.getRegClassIDOfValue(*(L->begin()))];
  58            RegClassList[ L->getRegClass()->getID() ];
  59
  60          RC-> addLRToIG( L );           // add this LR to an IG
  61        }
  62     }
  63   }
  64
  65                                         // init RegClassList
  66   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
  67     RegClassList[ rc ]->createInterferenceGraph();
  68
  69   if( DEBUG_RA)
  70     cout << "LRLists Created!" << endl;
  71 }
  72
  73
  74
  75 //----------------------------------------------------------------------------
  76 // This method will add all interferences at for a given instruction.
  77 // Interence occurs only if the LR of Def (Inst or Arg) is of the same reg
  78 // class as that of live var. The live var passed to this function is the
  79 // LVset AFTER the instruction
  80 //----------------------------------------------------------------------------
  81
  82 void PhyRegAlloc::addInterference(const Value *const Def,
  83                                   const LiveVarSet *const LVSet,
  84                                   const bool isCallInst) {
  85
  86   LiveVarSet::const_iterator LIt = LVSet->begin();
  87
  88   // get the live range of instruction
  89   const LiveRange *const LROfDef = LRI.getLiveRangeForValue( Def );
  90
  91   IGNode *const IGNodeOfDef = LROfDef->getUserIGNode();
  92   assert( IGNodeOfDef );
  93
  94   RegClass *const RCOfDef = LROfDef->getRegClass();
  95
  96   // for each live var in live variable set
  97   for( ; LIt != LVSet->end(); ++LIt) {
  98
  99     if( DEBUG_RA > 1) {
 100       cout << "< Def="; printValue(Def);
 101       cout << ", Lvar=";  printValue( *LIt); cout  << "> ";
 102     }
 103
 104     //  get the live range corresponding to live var
 105     LiveRange *const LROfVar = LRI.getLiveRangeForValue(*LIt );
 106
 107     // LROfVar can be null if it is a const since a const
 108     // doesn't have a dominating def - see Assumptions above
 109     if( LROfVar)   {
 110
 111       if(LROfDef == LROfVar)            // do not set interf for same LR
 112         continue;
 113
 114       // if 2 reg classes are the same set interference
 115       if( RCOfDef == LROfVar->getRegClass() ){
 116         RCOfDef->setInterference( LROfDef, LROfVar);
 117
 118       }
 119
 120       //the live range of this var interferes with this call
 121       if( isCallInst )
 122         LROfVar->addCallInterference( (const Instruction *const) Def );
 123
 124     }
 125     else if(DEBUG_RA > 1)  {
 126       // we will not have LRs for values not explicitly allocated in the
 127       // instruction stream (e.g., constants)
 128       cout << " warning: no live range for " ;
 129       printValue( *LIt); cout << endl; }
 130
 131   }
 132
 133 }
 134
 135 //----------------------------------------------------------------------------
 136 // This method will walk thru code and create interferences in the IG of
 137 // each RegClass.
 138 //----------------------------------------------------------------------------
 139
 140 void PhyRegAlloc::buildInterferenceGraphs()
 141 {
 142
 143   if(DEBUG_RA) cout << "Creating interference graphs ..." << endl;
 144
 145   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 146
 147   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 148
 149     // get the iterator for machine instructions
 150     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 151     MachineCodeForBasicBlock::const_iterator
 152       MInstIterator = MIVec.begin();
 153
 154     // iterate over all the machine instructions in BB
 155     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 156
 157       const MachineInstr *const MInst = *MInstIterator;
 158
 159       // get the LV set after the instruction
 160       const LiveVarSet *const LVSetAI =
 161         LVI->getLiveVarSetAfterMInst(MInst, *BBI);
 162
 163       const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
 164
 165       // iterate over  MI operands to find defs
 166       for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); ++OpI) {
 167
 168         if( OpI.isDef() ) {
 169           // create a new LR iff this operand is a def
 170           addInterference(*OpI, LVSetAI, isCallInst );
 171
 172         } //if this is a def
 173
 174       } // for all operands
 175
 176     } // for all machine instructions in BB
 177
 178
 179     // go thru LLVM instructions in the basic block and record all CALL
 180     // instructions in the CallInstrList
 181     BasicBlock::const_iterator InstIt = (*BBI)->begin();
 182
 183     for( ; InstIt != (*BBI)->end() ; ++ InstIt) {
 184
 185       if( (*InstIt)->getOpcode() == Instruction::Call )
 186         CallInstrList.push_back( *InstIt );
 187    }
 188
 189   } // for all BBs in method
 190
 191
 192   // add interferences for method arguments. Since there are no explict
 193   // defs in method for args, we have to add them manually
 194
 195   addInterferencesForArgs();            // add interference for method args
 196
 197   if( DEBUG_RA)
 198     cout << "Interference graphs calculted!" << endl;
 199
 200 }
 201
 202
 203
 204
 205 //----------------------------------------------------------------------------
 206 // This method will add interferences for incoming arguments to a method.
 207 //----------------------------------------------------------------------------
 208 void PhyRegAlloc::addInterferencesForArgs()
 209 {
 210                                               // get the InSet of root BB
 211   const LiveVarSet *const InSet = LVI->getInSetOfBB( Meth->front() );
 212
 213                                               // get the argument list
 214   const Method::ArgumentListType& ArgList = Meth->getArgumentList();
 215
 216                                               // get an iterator to arg list
 217   Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
 218
 219
 220   for( ; ArgIt != ArgList.end() ; ++ArgIt) {  // for each argument
 221     addInterference( *ArgIt, InSet, false );  // add interferences between
 222                                               // args and LVars at start
 223     if( DEBUG_RA > 1) {
 224       cout << " - %% adding interference for  argument ";
 225       printValue( (const Value *) *ArgIt); cout  << endl;
 226     }
 227   }
 228 }
 229
 230
 231 //----------------------------------------------------------------------------
 232 // This method is called after register allocation is complete to set the
 233 // allocated reisters in the machine code. This code will add register numbers
 234 // to MachineOperands that contain a Value.
 235 //----------------------------------------------------------------------------
 236
 237 void PhyRegAlloc::updateMachineCode()
 238 {
 239
 240   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 241
 242   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 243
 244     // get the iterator for machine instructions
 245     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 246     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 247
 248     // iterate over all the machine instructions in BB
 249     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 250
 251       MachineInstr *const MInst = *MInstIterator;
 252
 253       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 254
 255       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 256
 257         MachineOperand& Op = MInst->getOperand(OpNum);
 258
 259         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 260             Op.getOperandType() ==  MachineOperand::MO_CCRegister) {
 261
 262           const Value *const Val =  Op.getVRegValue();
 263
 264           // delete this condition checking later (must assert if Val is null)
 265           if( !Val ) {
 266             cout << "Error: NULL Value found in instr." << endl;
 267             Op.setRegForValue( 10000 ); // an invalid value is set
 268             continue;
 269           }
 270           assert( Val && "Value is NULL");
 271
 272           const LiveRange *const LR = LRI.getLiveRangeForValue(Val);
 273
 274           if ( !LR ) {
 275             if( ! ( (Val->getType())->isLabelType() ||
 276                     (Val->getValueType() == Value::ConstantVal) ) ) {
 277               cout << "Warning: No LiveRange for: ";
 278               printValue( Val); cout << endl;
 279             }
 280
 281             //assert( LR && "No LR found for Value");
 282             continue;
 283           }
 284
 285           unsigned RCID = (LR->getRegClass())->getID();
 286
 287           Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) );
 288
 289           int RegNum = MRI.getUnifiedRegNum(RCID, LR->getColor());
 290
 291         }
 292       }
 293
 294     }
 295   }
 296 }
 297
 298
 299
 300
 301 //----------------------------------------------------------------------------
 302 // This method prints the code with registers after register allocation is
 303 // complete.
 304 //----------------------------------------------------------------------------
 305 void PhyRegAlloc::printMachineCode()
 306 {
 307
 308   cout << endl << ";************** Method ";
 309   cout << Meth->getName() << " *****************" << endl;
 310
 311   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 312
 313   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 314
 315     cout << endl ; printLabel( *BBI); cout << ": ";
 316
 317     // get the iterator for machine instructions
 318     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 319     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 320
 321     // iterate over all the machine instructions in BB
 322     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 323
 324       MachineInstr *const MInst = *MInstIterator;
 325
 326
 327       cout << endl << "\t";
 328       cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 329
 330
 331       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 332
 333       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 334
 335         MachineOperand& Op = MInst->getOperand(OpNum);
 336
 337         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 338             Op.getOperandType() ==  MachineOperand::MO_CCRegister ||
 339             Op.getOperandType() ==  MachineOperand::MO_MachineRegister ) {
 340
 341           const int RegNum = (const int) Op.getAllocatedRegNum();
 342
 343           // ****this code is temporary till NULL Values are fixed
 344           if( RegNum == 10000) {
 345             cout << "\t<*NULL Value*>";
 346             continue;
 347           }
 348
 349           cout << "\t" << "%" << MRI.getUnifiedRegName( RegNum);
 350
 351         }
 352         else if( Op.getOperandType() ==  MachineOperand::MO_PCRelativeDisp ) {
 353           const Value *const Val = Op.getVRegValue () ;
 354           if( !Val ) {
 355             cout << "\t<*NULL Value*>";
 356             continue;
 357           }
 358           if( (Val->getValueType() == Value::BasicBlockVal))
 359             { cout << "\t"; printLabel( Op.getVRegValue () ); }
 360           else { cout << "\t"; printValue( Val ); }
 361         }
 362
 363         else
 364           cout << "\t" << Op;      // use dump field
 365       }
 366
 367     }
 368
 369     cout << endl;
 370
 371   }
 372
 373   cout << endl;
 374 }
 375
 376 void PhyRegAlloc::printLabel(const Value *const Val)
 377 {
 378   if( Val->hasName() )
 379     cout  << Val->getName();
 380   else
 381     cout << "Label" <<  Val;
 382 }
 383
 384
 385
 386
 387
 388
 389
 390
 391 void PhyRegAlloc::allocateRegisters()
 392 {
 393   constructLiveRanges();                // create LR info
 394
 395   if( DEBUG_RA)
 396     LRI.printLiveRanges();
 397
 398   createIGNodeListsAndIGs();            // create IGNode list and IGs
 399
 400   buildInterferenceGraphs();            // build IGs in all reg classes
 401
 402
 403   if( DEBUG_RA) {
 404     // print all LRs in all reg classes
 405     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
 406       RegClassList[ rc ]->printIGNodeList();
 407
 408     // print IGs in all register classes
 409     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 410       RegClassList[ rc ]->printIG();
 411   }
 412
 413   LRI.coalesceLRs();                    // coalesce all live ranges
 414
 415   if( DEBUG_RA) {
 416     // print all LRs in all reg classes
 417     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
 418       RegClassList[ rc ]->printIGNodeList();
 419
 420     // print IGs in all register classes
 421     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 422       RegClassList[ rc ]->printIG();
 423   }
 424
 425   MRI.colorArgs(Meth, LRI);             // color method args
 426                                         // color call args of call instrns
 427   MRI.colorCallArgs(CallInstrList, LRI, AddedInstrMap);
 428
 429                                         // color all register classes
 430   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 431     RegClassList[ rc ]->colorAllRegs();
 432
 433   updateMachineCode();
 434   PrintMachineInstructions(Meth);
 435   printMachineCode();                   // only for DEBUGGING
 436 }
 437