lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp

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