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 <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), 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
  52 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) {
  53   assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor()));
  54   set_union(*L1, *L2);                   // add elements of L2 to L1
  55
  56   for(ValueSet::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) {
  57     //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
  58
  59     L1->insert(*L2It);                  // add the var in L2 to L1
  60     LiveRangeMap[*L2It] = L1;         // now the elements in L2 should map
  61                                         //to L1
  62   }
  63
  64
  65   // Now if LROfDef(L1) has a suggested color, it will remain.
  66   // But, if LROfUse(L2) has a suggested color, the new range
  67   // must have the same color.
  68
  69   if(L2->hasSuggestedColor())
  70     L1->setSuggestedColor(L2->getSuggestedColor());
  71
  72
  73   if (L2->isCallInterference())
  74     L1->setCallInterference();
  75
  76   // add the spill costs
  77   L1->addSpillCost(L2->getSpillCost());
  78
  79   delete L2;                        // delete L2 as it is no longer needed
  80 }
  81
  82
  83
  84 //---------------------------------------------------------------------------
  85 // Method for constructing all live ranges in a method. It creates live
  86 // ranges for all values defined in the instruction stream. Also, it
  87 // creates live ranges for all incoming arguments of the method.
  88 //---------------------------------------------------------------------------
  89 void LiveRangeInfo::constructLiveRanges()
  90 {
  91
  92   if( DEBUG_RA)
  93     cerr << "Consturcting Live Ranges ...\n";
  94
  95   // first find the live ranges for all incoming args of the method since
  96   // those LRs start from the start of the method
  97
  98                                                  // get the argument list
  99   const Method::ArgumentListType& ArgList = Meth->getArgumentList();
 100                                                  // get an iterator to arg list
 101   Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
 102
 103
 104   for( ; ArgIt != ArgList.end() ; ++ArgIt) {     // for each argument
 105     LiveRange * ArgRange = new LiveRange();      // creates a new LR and
 106     const Value *Val = (const Value *) *ArgIt;
 107
 108     ArgRange->insert(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            << RAV((const Value *)*ArgIt) << "\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                  << RAV(OpI.getMachineOperand().getVRegValue()) << "\n";
 167         }
 168
 169         // create a new LR iff this operand is a def
 170         if (OpI.isDef()) {
 171           const Value *Def = *OpI;
 172
 173           // Only instruction values are accepted for live ranges here
 174           if (Def->getValueType() != Value::InstructionVal ) {
 175             cerr << "\n**%%Error: Def is not an instruction val. Def="
 176                  << RAV(Def) << "\n";
 177             continue;
 178           }
 179
 180           LiveRange *DefRange = LiveRangeMap[Def];
 181
 182           // see LR already there (because of multiple defs)
 183           if( !DefRange) {                  // if it is not in LiveRangeMap
 184             DefRange = new LiveRange();     // creates a new live range and
 185             DefRange->insert(Def);          // add the instruction (def) to it
 186             LiveRangeMap[ Def ] = DefRange; // update the map
 187
 188             if (DEBUG_RA > 1)
 189               cerr << "  creating a LR for def: " << RAV(Def) << "\n";
 190
 191             // set the register class of the new live range
 192             //assert( RegClassList.size() );
 193             MachineOperand::MachineOperandType OpTy =
 194               OpI.getMachineOperand().getOperandType();
 195
 196             bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
 197             unsigned rcid = MRI.getRegClassIDOfValue(
 198                             OpI.getMachineOperand().getVRegValue(), isCC );
 199
 200
 201             if (isCC && DEBUG_RA)
 202               cerr  << "\a**created a LR for a CC reg:"
 203                     << RAV(OpI.getMachineOperand().getVRegValue());
 204
 205             DefRange->setRegClass(RegClassList[rcid]);
 206           } else {
 207             DefRange->insert(Def);          // add the opearand to def range
 208                                             // update the map - Operand points
 209                                             // to the merged set
 210             LiveRangeMap[Def] = DefRange;
 211
 212             if (DEBUG_RA > 1)
 213               cerr << "   added to an existing LR for def: "
 214                    << RAV(Def) << "\n";
 215           }
 216
 217         } // if isDef()
 218
 219       } // for all opereands in machine instructions
 220
 221     } // for all machine instructions in the BB
 222
 223   } // for all BBs in method
 224
 225
 226   // Now we have to suggest clors for call and return arg live ranges.
 227   // Also, if there are implicit defs (e.g., retun value of a call inst)
 228   // they must be added to the live range list
 229
 230   suggestRegs4CallRets();
 231
 232   if( DEBUG_RA)
 233     cerr << "Initial Live Ranges constructed!\n";
 234
 235 }
 236
 237
 238 //---------------------------------------------------------------------------
 239 // If some live ranges must be colored with specific hardware registers
 240 // (e.g., for outgoing call args), suggesting of colors for such live
 241 // ranges is done using target specific method. Those methods are called
 242 // from this function. The target specific methods must:
 243 //    1) suggest colors for call and return args.
 244 //    2) create new LRs for implicit defs in machine instructions
 245 //---------------------------------------------------------------------------
 246 void LiveRangeInfo::suggestRegs4CallRets()
 247 {
 248
 249   CallRetInstrListType::const_iterator It =  CallRetInstrList.begin();
 250
 251   for( ; It !=  CallRetInstrList.end(); ++It ) {
 252
 253     const MachineInstr *MInst = *It;
 254     MachineOpCode OpCode =  MInst->getOpCode();
 255
 256     if( (TM.getInstrInfo()).isReturn(OpCode)  )
 257       MRI.suggestReg4RetValue( MInst, *this);
 258
 259     else if( (TM.getInstrInfo()).isCall( OpCode ) )
 260       MRI.suggestRegs4CallArgs( MInst, *this, RegClassList );
 261
 262     else
 263       assert( 0 && "Non call/ret instr in  CallRetInstrList" );
 264   }
 265
 266 }
 267
 268
 269 //--------------------------------------------------------------------------
 270 // The following method coalesces live ranges when possible. This method
 271 // must be called after the interference graph has been constructed.
 272
 273
 274 /* Algorithm:
 275    for each BB in method
 276      for each machine instruction (inst)
 277        for each definition (def) in inst
 278          for each operand (op) of inst that is a use
 279            if the def and op are of the same register type
 280              if the def and op do not interfere //i.e., not simultaneously live
 281                if (degree(LR of def) + degree(LR of op)) <= # avail regs
 282                  if both LRs do not have suggested colors
 283                     merge2IGNodes(def, op) // i.e., merge 2 LRs
 284
 285 */
 286 //---------------------------------------------------------------------------
 287 void LiveRangeInfo::coalesceLRs()
 288 {
 289   if( DEBUG_RA)
 290     cerr << "\nCoalscing LRs ...\n";
 291
 292   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 293
 294   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 295
 296     // get the iterator for machine instructions
 297     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 298     MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
 299
 300     // iterate over all the machine instructions in BB
 301     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 302
 303       const MachineInstr * MInst = *MInstIterator;
 304
 305       if( DEBUG_RA > 1) {
 306         cerr << " *Iterating over machine instr ";
 307         MInst->dump();
 308         cerr << "\n";
 309       }
 310
 311
 312       // iterate over  MI operands to find defs
 313       for(MachineInstr::val_const_op_iterator DefI(MInst);!DefI.done();++DefI){
 314
 315         if( DefI.isDef() ) {            // iff this operand is a def
 316
 317           LiveRange *const LROfDef = getLiveRangeForValue( *DefI );
 318           assert( LROfDef );
 319           RegClass *const RCOfDef = LROfDef->getRegClass();
 320
 321           MachineInstr::val_const_op_iterator UseI(MInst);
 322           for( ; !UseI.done(); ++UseI){ // for all uses
 323
 324             LiveRange *const LROfUse = getLiveRangeForValue( *UseI );
 325
 326             if( ! LROfUse ) {           // if LR of use is not found
 327
 328               //don't warn about labels
 329               if (!((*UseI)->getType())->isLabelType() && DEBUG_RA)
 330                 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
 331               continue;                 // ignore and continue
 332             }
 333
 334             if( LROfUse == LROfDef)     // nothing to merge if they are same
 335               continue;
 336
 337             //RegClass *const RCOfUse = LROfUse->getRegClass();
 338             //if( RCOfDef == RCOfUse ) {  // if the reg classes are the same
 339
 340             if( MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse) ) {
 341
 342               // If the two RegTypes are the same
 343
 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
 352                   // if both LRs do not have suggested colors
 353                   if( ! (LROfDef->hasSuggestedColor() &&
 354                          LROfUse->hasSuggestedColor() ) ) {
 355
 356                     RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
 357                     unionAndUpdateLRs(LROfDef, LROfUse);
 358                   }
 359
 360
 361                 } // if combined degree is less than # of regs
 362
 363               } // if def and use do not interfere
 364
 365             }// if reg classes are the same
 366
 367           } // for all uses
 368
 369         } // if def
 370
 371       } // for all defs
 372
 373     } // for all machine instructions
 374
 375   } // for all BBs
 376
 377   if( DEBUG_RA)
 378     cerr << "\nCoalscing Done!\n";
 379
 380 }
 381
 382
 383
 384
 385
 386 /*--------------------------- Debug code for printing ---------------*/
 387
 388
 389 void LiveRangeInfo::printLiveRanges() {
 390   LiveRangeMapType::iterator HMI = LiveRangeMap.begin();   // hash map iterator
 391   cerr << "\nPrinting Live Ranges from Hash Map:\n";
 392   for( ; HMI != LiveRangeMap.end(); ++HMI) {
 393     if (HMI->first && HMI->second) {
 394       cerr << " " << RAV(HMI->first) << "\t: ";
 395       printSet(*HMI->second); cerr << "\n";
 396     }
 397   }
 398 }
 399
 400