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