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