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