lib/Target/SparcV9/RegAlloc/LiveRangeInfo.cpp

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