lib/CodeGen/RegAlloc/LiveRangeInfo.cpp

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