lib/Target/SparcV9/RegAlloc/LiveRangeInfo.cpp

   1 #include "llvm/CodeGen/LiveRangeInfo.h"
   2 #include <iostream>
   3 using std::cerr;
   4
   5 //---------------------------------------------------------------------------
   6 // Constructor
   7 //---------------------------------------------------------------------------
   8 LiveRangeInfo::LiveRangeInfo(const Method *const M,
   9                              const TargetMachine& tm,
  10                              std::vector<RegClass *> &RCL)
  11                              : Meth(M), LiveRangeMap(), TM(tm),
  12                                RegClassList(RCL), MRI(tm.getRegInfo())
  13 { }
  14
  15
  16 //---------------------------------------------------------------------------
  17 // Destructor: Deletes all LiveRanges in the LiveRangeMap
  18 //---------------------------------------------------------------------------
  19 LiveRangeInfo::~LiveRangeInfo() {
  20   LiveRangeMapType::iterator MI =  LiveRangeMap.begin();
  21
  22   for( ; MI != LiveRangeMap.end() ; ++MI) {
  23     if (MI->first && MI->second) {
  24       LiveRange *LR = MI->second;
  25
  26       // we need to be careful in deleting LiveRanges in LiveRangeMap
  27       // since two/more Values in the live range map can point to the same
  28       // live range. We have to make the other entries NULL when we delete
  29       // a live range.
  30
  31       LiveRange::iterator LI = LR->begin();
  32
  33       for( ; LI != LR->end() ; ++LI)
  34         LiveRangeMap[*LI] = 0;
  35
  36       delete LR;
  37     }
  38   }
  39 }
  40
  41
  42 //---------------------------------------------------------------------------
  43 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
  44 // Note: the caller must make sure that L1 and L2 are distinct and both
  45 // LRs don't have suggested colors
  46 //---------------------------------------------------------------------------
  47 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *const L1, LiveRange *L2)
  48 {
  49   assert( L1 != L2);
  50   L1->setUnion( L2 );                   // add elements of L2 to L1
  51   ValueSet::iterator L2It;
  52
  53   for( L2It = L2->begin() ; L2It != L2->end(); ++L2It) {
  54
  55     //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
  56
  57     L1->add( *L2It );                   // add the var in L2 to L1
  58     LiveRangeMap[ *L2It ] = L1;         // now the elements in L2 should map
  59                                         //to L1
  60   }
  61
  62
  63   // Now if LROfDef(L1) has a suggested color, it will remain.
  64   // But, if LROfUse(L2) has a suggested color, the new range
  65   // must have the same color.
  66
  67   if(L2->hasSuggestedColor())
  68     L1->setSuggestedColor( L2->getSuggestedColor() );
  69
  70
  71   if( L2->isCallInterference() )
  72     L1->setCallInterference();
  73
  74
  75   L1->addSpillCost( L2->getSpillCost() ); // add the spill costs
  76
  77   delete L2;                        // delete L2 as it is no longer needed
  78 }
  79
  80
  81
  82 //---------------------------------------------------------------------------
  83 // Method for constructing all live ranges in a method. It creates live
  84 // ranges for all values defined in the instruction stream. Also, it
  85 // creates live ranges for all incoming arguments of the method.
  86 //---------------------------------------------------------------------------
  87 void LiveRangeInfo::constructLiveRanges()
  88 {
  89
  90   if( DEBUG_RA)
  91     cerr << "Consturcting Live Ranges ...\n";
  92
  93   // first find the live ranges for all incoming args of the method since
  94   // those LRs start from the start of the method
  95
  96                                                  // get the argument list
  97   const Method::ArgumentListType& ArgList = Meth->getArgumentList();
  98                                                  // get an iterator to arg list
  99   Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
 100
 101
 102   for( ; ArgIt != ArgList.end() ; ++ArgIt) {     // for each argument
 103     LiveRange * ArgRange = new LiveRange();      // creates a new LR and
 104     const Value *const Val = (const Value *) *ArgIt;
 105
 106     assert( Val);
 107
 108     ArgRange->add(Val);     // add the arg (def) to it
 109     LiveRangeMap[Val] = ArgRange;
 110
 111     // create a temp machine op to find the register class of value
 112     //const MachineOperand Op(MachineOperand::MO_VirtualRegister);
 113
 114     unsigned rcid = MRI.getRegClassIDOfValue( Val );
 115     ArgRange->setRegClass(RegClassList[ rcid ] );
 116
 117
 118     if( DEBUG_RA > 1) {
 119       cerr << " adding LiveRange for argument ";
 120       printValue((const Value *) *ArgIt); cerr << "\n";
 121     }
 122   }
 123
 124   // Now suggest hardware registers for these method args
 125   MRI.suggestRegs4MethodArgs(Meth, *this);
 126
 127
 128
 129   // Now find speical LLVM instructions (CALL, RET) and LRs in machine
 130   // instructions.
 131
 132
 133   Method::const_iterator BBI = Meth->begin();    // random iterator for BBs
 134   for( ; BBI != Meth->end(); ++BBI) {            // go thru BBs in random order
 135
 136     // Now find all LRs for machine the instructions. A new LR will be created
 137     // only for defs in the machine instr since, we assume that all Values are
 138     // defined before they are used. However, there can be multiple defs for
 139     // the same Value in machine instructions.
 140
 141     // get the iterator for machine instructions
 142     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 143     MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
 144
 145     // iterate over all the machine instructions in BB
 146     for( ; MInstIterator != MIVec.end(); MInstIterator++) {
 147
 148       const MachineInstr * MInst = *MInstIterator;
 149
 150       // Now if the machine instruction is a  call/return instruction,
 151       // add it to CallRetInstrList for processing its implicit operands
 152
 153       if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
 154          TM.getInstrInfo().isCall(MInst->getOpCode()))
 155         CallRetInstrList.push_back( MInst );
 156
 157
 158       // iterate over  MI operands to find defs
 159       for (MachineInstr::val_const_op_iterator OpI(MInst); !OpI.done(); ++OpI) {
 160         if(DEBUG_RA) {
 161           MachineOperand::MachineOperandType OpTyp =
 162             OpI.getMachineOperand().getOperandType();
 163
 164           if (OpTyp == MachineOperand::MO_CCRegister) {
 165             cerr << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:";
 166             printValue( OpI.getMachineOperand().getVRegValue() );
 167             cerr << "\n";
 168           }
 169         }
 170
 171         // create a new LR iff this operand is a def
 172         if( OpI.isDef() ) {
 173           const Value *const Def = *OpI;
 174
 175           // Only instruction values are accepted for live ranges here
 176           if( Def->getValueType() != Value::InstructionVal ) {
 177             cerr << "\n**%%Error: Def is not an instruction val. Def=";
 178             printValue( Def ); cerr << "\n";
 179             continue;
 180           }
 181
 182           LiveRange *DefRange = LiveRangeMap[Def];
 183
 184           // see LR already there (because of multiple defs)
 185           if( !DefRange) {                  // if it is not in LiveRangeMap
 186             DefRange = new LiveRange();     // creates a new live range and
 187             DefRange->add( Def );           // add the instruction (def) to it
 188             LiveRangeMap[ Def ] = DefRange; // update the map
 189
 190             if( DEBUG_RA > 1) {
 191               cerr << "  creating a LR for def: ";
 192               printValue(Def); cerr  << "\n";
 193             }
 194
 195             // set the register class of the new live range
 196             //assert( RegClassList.size() );
 197             MachineOperand::MachineOperandType OpTy =
 198               OpI.getMachineOperand().getOperandType();
 199
 200             bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
 201             unsigned rcid = MRI.getRegClassIDOfValue(
 202                             OpI.getMachineOperand().getVRegValue(), isCC );
 203
 204
 205             if(isCC && DEBUG_RA) {
 206               cerr  << "\a**created a LR for a CC reg:";
 207               printValue( OpI.getMachineOperand().getVRegValue() );
 208             }
 209
 210             DefRange->setRegClass( RegClassList[ rcid ] );
 211
 212           }
 213           else {
 214             DefRange->add( Def );           // add the opearand to def range
 215                                             // update the map - Operand points
 216                                             // to the merged set
 217             LiveRangeMap[ Def ] = DefRange;
 218
 219             if( DEBUG_RA > 1) {
 220               cerr << "   added to an existing LR for def: ";
 221               printValue( Def ); cerr  << "\n";
 222             }
 223           }
 224
 225         } // if isDef()
 226
 227       } // for all opereands in machine instructions
 228
 229     } // for all machine instructions in the BB
 230
 231   } // for all BBs in method
 232
 233
 234   // Now we have to suggest clors for call and return arg live ranges.
 235   // Also, if there are implicit defs (e.g., retun value of a call inst)
 236   // they must be added to the live range list
 237
 238   suggestRegs4CallRets();
 239
 240   if( DEBUG_RA)
 241     cerr << "Initial Live Ranges constructed!\n";
 242
 243 }
 244
 245
 246 //---------------------------------------------------------------------------
 247 // If some live ranges must be colored with specific hardware registers
 248 // (e.g., for outgoing call args), suggesting of colors for such live
 249 // ranges is done using target specific method. Those methods are called
 250 // from this function. The target specific methods must:
 251 //    1) suggest colors for call and return args.
 252 //    2) create new LRs for implicit defs in machine instructions
 253 //---------------------------------------------------------------------------
 254 void LiveRangeInfo::suggestRegs4CallRets()
 255 {
 256
 257   CallRetInstrListType::const_iterator It =  CallRetInstrList.begin();
 258
 259   for( ; It !=  CallRetInstrList.end(); ++It ) {
 260
 261     const MachineInstr *MInst = *It;
 262     MachineOpCode OpCode =  MInst->getOpCode();
 263
 264     if( (TM.getInstrInfo()).isReturn(OpCode)  )
 265       MRI.suggestReg4RetValue( MInst, *this);
 266
 267     else if( (TM.getInstrInfo()).isCall( OpCode ) )
 268       MRI.suggestRegs4CallArgs( MInst, *this, RegClassList );
 269
 270     else
 271       assert( 0 && "Non call/ret instr in  CallRetInstrList" );
 272   }
 273
 274 }
 275
 276
 277 //--------------------------------------------------------------------------
 278 // The following method coalesces live ranges when possible. This method
 279 // must be called after the interference graph has been constructed.
 280
 281
 282 /* Algorithm:
 283    for each BB in method
 284      for each machine instruction (inst)
 285        for each definition (def) in inst
 286          for each operand (op) of inst that is a use
 287            if the def and op are of the same register type
 288              if the def and op do not interfere //i.e., not simultaneously live
 289                if (degree(LR of def) + degree(LR of op)) <= # avail regs
 290                  if both LRs do not have suggested colors
 291                     merge2IGNodes(def, op) // i.e., merge 2 LRs
 292
 293 */
 294 //---------------------------------------------------------------------------
 295 void LiveRangeInfo::coalesceLRs()
 296 {
 297   if( DEBUG_RA)
 298     cerr << "\nCoalscing LRs ...\n";
 299
 300   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 301
 302   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 303
 304     // get the iterator for machine instructions
 305     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 306     MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
 307
 308     // iterate over all the machine instructions in BB
 309     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 310
 311       const MachineInstr * MInst = *MInstIterator;
 312
 313       if( DEBUG_RA > 1) {
 314         cerr << " *Iterating over machine instr ";
 315         MInst->dump();
 316         cerr << "\n";
 317       }
 318
 319
 320       // iterate over  MI operands to find defs
 321       for(MachineInstr::val_const_op_iterator DefI(MInst);!DefI.done();++DefI){
 322
 323         if( DefI.isDef() ) {            // iff this operand is a def
 324
 325           LiveRange *const LROfDef = getLiveRangeForValue( *DefI );
 326           assert( LROfDef );
 327           RegClass *const RCOfDef = LROfDef->getRegClass();
 328
 329           MachineInstr::val_const_op_iterator UseI(MInst);
 330           for( ; !UseI.done(); ++UseI){ // for all uses
 331
 332             LiveRange *const LROfUse = getLiveRangeForValue( *UseI );
 333
 334             if( ! LROfUse ) {           // if LR of use is not found
 335
 336               //don't warn about labels
 337               if (!((*UseI)->getType())->isLabelType() && DEBUG_RA) {
 338                 cerr<<" !! Warning: No LR for use "; printValue(*UseI);
 339                 cerr << "\n";
 340               }
 341               continue;                 // ignore and continue
 342             }
 343
 344             if( LROfUse == LROfDef)     // nothing to merge if they are same
 345               continue;
 346
 347             //RegClass *const RCOfUse = LROfUse->getRegClass();
 348             //if( RCOfDef == RCOfUse ) {  // if the reg classes are the same
 349
 350             if( MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse) ) {
 351
 352               // If the two RegTypes are the same
 353
 354               if( ! RCOfDef->getInterference(LROfDef, LROfUse) ) {
 355
 356                 unsigned CombinedDegree =
 357                   LROfDef->getUserIGNode()->getNumOfNeighbors() +
 358                   LROfUse->getUserIGNode()->getNumOfNeighbors();
 359
 360                 if( CombinedDegree <= RCOfDef->getNumOfAvailRegs() ) {
 361
 362                   // if both LRs do not have suggested colors
 363                   if( ! (LROfDef->hasSuggestedColor() &&
 364                          LROfUse->hasSuggestedColor() ) ) {
 365
 366                     RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
 367                     unionAndUpdateLRs(LROfDef, LROfUse);
 368                   }
 369
 370
 371                 } // if combined degree is less than # of regs
 372
 373               } // if def and use do not interfere
 374
 375             }// if reg classes are the same
 376
 377           } // for all uses
 378
 379         } // if def
 380
 381       } // for all defs
 382
 383     } // for all machine instructions
 384
 385   } // for all BBs
 386
 387   if( DEBUG_RA)
 388     cerr << "\nCoalscing Done!\n";
 389
 390 }
 391
 392
 393
 394
 395
 396 /*--------------------------- Debug code for printing ---------------*/
 397
 398
 399 void LiveRangeInfo::printLiveRanges()
 400 {
 401   LiveRangeMapType::iterator HMI = LiveRangeMap.begin();   // hash map iterator
 402   cerr << "\nPrinting Live Ranges from Hash Map:\n";
 403   for( ; HMI != LiveRangeMap.end() ; ++HMI) {
 404     if( HMI->first && HMI->second ) {
 405       cerr <<" "; printValue((*HMI).first);  cerr << "\t: ";
 406       HMI->second->printSet(); cerr << "\n";
 407     }
 408   }
 409 }
 410
 411