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