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