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