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