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 "LiveRangeInfo.h"
   8 #include "RegAllocCommon.h"
   9 #include "RegClass.h"
  10 #include "IGNode.h"
  11 #include "llvm/CodeGen/MachineInstr.h"
  12 #include "llvm/CodeGen/MachineFunction.h"
  13 #include "llvm/Target/TargetMachine.h"
  14 #include "llvm/Target/TargetInstrInfo.h"
  15 #include "llvm/Target/TargetRegInfo.h"
  16 #include "llvm/Function.h"
  17 #include "Support/SetOperations.h"
  18
  19 unsigned LiveRange::getRegClassID() const { return getRegClass()->getID(); }
  20
  21 LiveRangeInfo::LiveRangeInfo(const Function *F, const TargetMachine &tm,
  22                              std::vector<RegClass *> &RCL)
  23   : Meth(F), TM(tm), RegClassList(RCL), MRI(tm.getRegInfo()) { }
  24
  25
  26 LiveRangeInfo::~LiveRangeInfo() {
  27   for (LiveRangeMapType::iterator MI = LiveRangeMap.begin();
  28        MI != LiveRangeMap.end(); ++MI) {
  29
  30     if (MI->first && MI->second) {
  31       LiveRange *LR = MI->second;
  32
  33       // we need to be careful in deleting LiveRanges in LiveRangeMap
  34       // since two/more Values in the live range map can point to the same
  35       // live range. We have to make the other entries NULL when we delete
  36       // a live range.
  37
  38       for (LiveRange::iterator LI = LR->begin(); LI != LR->end(); ++LI)
  39         LiveRangeMap[*LI] = 0;
  40
  41       delete LR;
  42     }
  43   }
  44 }
  45
  46
  47 //---------------------------------------------------------------------------
  48 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
  49 // Note: the caller must make sure that L1 and L2 are distinct and both
  50 // LRs don't have suggested colors
  51 //---------------------------------------------------------------------------
  52
  53 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) {
  54   assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor()));
  55   assert(! (L1->hasColor() && L2->hasColor()) ||
  56          L1->getColor() == L2->getColor());
  57
  58   set_union(*L1, *L2);                   // add elements of L2 to L1
  59
  60   for(ValueSet::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) {
  61     //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
  62
  63     L1->insert(*L2It);                  // add the var in L2 to L1
  64     LiveRangeMap[*L2It] = L1;           // now the elements in L2 should map
  65                                         //to L1
  66   }
  67
  68   // set call interference for L1 from L2
  69   if (L2->isCallInterference())
  70     L1->setCallInterference();
  71
  72   // add the spill costs
  73   L1->addSpillCost(L2->getSpillCost());
  74
  75   // If L2 has a color, give L1 that color.  Note that L1 may have had the same
  76   // color or none, but would not have a different color as asserted above.
  77   if (L2->hasColor())
  78     L1->setColor(L2->getColor());
  79
  80   // Similarly, if LROfUse(L2) has a suggested color, the new range
  81   // must have the same color.
  82   if (L2->hasSuggestedColor())
  83     L1->setSuggestedColor(L2->getSuggestedColor());
  84
  85   delete L2;                        // delete L2 as it is no longer needed
  86 }
  87
  88
  89 //---------------------------------------------------------------------------
  90 // Method for creating a single live range for a definition.
  91 // The definition must be represented by a virtual register (a Value).
  92 // Note: this function does *not* check that no live range exists for def.
  93 //---------------------------------------------------------------------------
  94
  95 LiveRange*
  96 LiveRangeInfo::createNewLiveRange(const Value* Def, bool isCC /* = false*/)
  97 {
  98   LiveRange* DefRange = new LiveRange();  // Create a new live range,
  99   DefRange->insert(Def);                  // add Def to it,
 100   LiveRangeMap[Def] = DefRange;           // and update the map.
 101
 102   // set the register class of the new live range
 103   DefRange->setRegClass(RegClassList[MRI.getRegClassIDOfType(Def->getType(),
 104                                                              isCC)]);
 105
 106   if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
 107     std::cerr << "  Creating a LR for def ";
 108     if (isCC) std::cerr << " (CC Register!)";
 109     std::cerr << " : " << RAV(Def) << "\n";
 110   }
 111   return DefRange;
 112 }
 113
 114
 115 LiveRange*
 116 LiveRangeInfo::createOrAddToLiveRange(const Value* Def, bool isCC /* = false*/)
 117 {
 118   LiveRange *DefRange = LiveRangeMap[Def];
 119
 120   // check if the LR is already there (because of multiple defs)
 121   if (!DefRange) {
 122     DefRange = createNewLiveRange(Def, isCC);
 123   } else {                          // live range already exists
 124     DefRange->insert(Def);          // add the operand to the range
 125     LiveRangeMap[Def] = DefRange;   // make operand point to merged set
 126     if (DEBUG_RA >= RA_DEBUG_LiveRanges)
 127       std::cerr << "   Added to existing LR for def: " << RAV(Def) << "\n";
 128   }
 129   return DefRange;
 130 }
 131
 132
 133 //---------------------------------------------------------------------------
 134 // Method for constructing all live ranges in a function. It creates live
 135 // ranges for all values defined in the instruction stream. Also, it
 136 // creates live ranges for all incoming arguments of the function.
 137 //---------------------------------------------------------------------------
 138 void LiveRangeInfo::constructLiveRanges() {
 139
 140   if (DEBUG_RA >= RA_DEBUG_LiveRanges)
 141     std::cerr << "Constructing Live Ranges ...\n";
 142
 143   // first find the live ranges for all incoming args of the function since
 144   // those LRs start from the start of the function
 145   for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI)
 146     createNewLiveRange(AI, /*isCC*/ false);
 147
 148   // Now suggest hardware registers for these function args
 149   MRI.suggestRegs4MethodArgs(Meth, *this);
 150
 151   // Now create LRs for machine instructions.  A new LR will be created
 152   // only for defs in the machine instr since, we assume that all Values are
 153   // defined before they are used. However, there can be multiple defs for
 154   // the same Value in machine instructions.
 155   //
 156   // Also, find CALL and RETURN instructions, which need extra work.
 157   //
 158   MachineFunction &MF = MachineFunction::get(Meth);
 159   for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
 160     MachineBasicBlock &MBB = *BBI;
 161
 162     // iterate over all the machine instructions in BB
 163     for(MachineBasicBlock::iterator MInstIterator = MBB.begin();
 164         MInstIterator != MBB.end(); ++MInstIterator) {
 165       MachineInstr *MInst = *MInstIterator;
 166
 167       // If the machine instruction is a  call/return instruction, add it to
 168       // CallRetInstrList for processing its args, ret value, and ret addr.
 169       //
 170       if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
 171          TM.getInstrInfo().isCall(MInst->getOpCode()))
 172         CallRetInstrList.push_back(MInst);
 173
 174       // iterate over explicit MI operands and create a new LR
 175       // for each operand that is defined by the instruction
 176       for (MachineInstr::val_op_iterator OpI = MInst->begin(),
 177              OpE = MInst->end(); OpI != OpE; ++OpI)
 178         if (OpI.isDefOnly() || OpI.isDefAndUse()) {
 179           const Value *Def = *OpI;
 180           bool isCC = (OpI.getMachineOperand().getType()
 181                        == MachineOperand::MO_CCRegister);
 182           LiveRange* LR = createOrAddToLiveRange(Def, isCC);
 183
 184           // If the operand has a pre-assigned register,
 185           // set it directly in the LiveRange
 186           if (OpI.getMachineOperand().hasAllocatedReg()) {
 187             unsigned getClassId;
 188             LR->setColor(MRI.getClassRegNum(
 189                                 OpI.getMachineOperand().getAllocatedRegNum(),
 190                                 getClassId));
 191           }
 192         }
 193
 194       // iterate over implicit MI operands and create a new LR
 195       // for each operand that is defined by the instruction
 196       for (unsigned i = 0; i < MInst->getNumImplicitRefs(); ++i)
 197         if (MInst->getImplicitOp(i).opIsDefOnly() ||
 198             MInst->getImplicitOp(i).opIsDefAndUse()) {
 199           const Value *Def = MInst->getImplicitRef(i);
 200           LiveRange* LR = createOrAddToLiveRange(Def, /*isCC*/ false);
 201
 202           // If the implicit operand has a pre-assigned register,
 203           // set it directly in the LiveRange
 204           if (MInst->getImplicitOp(i).hasAllocatedReg()) {
 205             unsigned getClassId;
 206             LR->setColor(MRI.getClassRegNum(
 207                                 MInst->getImplicitOp(i).getAllocatedRegNum(),
 208                                 getClassId));
 209           }
 210         }
 211
 212     } // for all machine instructions in the BB
 213
 214   } // for all BBs in function
 215
 216   // Now we have to suggest clors for call and return arg live ranges.
 217   // Also, if there are implicit defs (e.g., retun value of a call inst)
 218   // they must be added to the live range list
 219   //
 220   suggestRegs4CallRets();
 221
 222   if( DEBUG_RA >= RA_DEBUG_LiveRanges)
 223     std::cerr << "Initial Live Ranges constructed!\n";
 224 }
 225
 226
 227 //---------------------------------------------------------------------------
 228 // If some live ranges must be colored with specific hardware registers
 229 // (e.g., for outgoing call args), suggesting of colors for such live
 230 // ranges is done using target specific function. Those functions are called
 231 // from this function. The target specific methods must:
 232 //    1) suggest colors for call and return args.
 233 //    2) create new LRs for implicit defs in machine instructions
 234 //---------------------------------------------------------------------------
 235 void LiveRangeInfo::suggestRegs4CallRets() {
 236   std::vector<MachineInstr*>::iterator It = CallRetInstrList.begin();
 237   for( ; It != CallRetInstrList.end(); ++It) {
 238     MachineInstr *MInst = *It;
 239     MachineOpCode OpCode = MInst->getOpCode();
 240
 241     if ((TM.getInstrInfo()).isReturn(OpCode))
 242       MRI.suggestReg4RetValue(MInst, *this);
 243     else if ((TM.getInstrInfo()).isCall(OpCode))
 244       MRI.suggestRegs4CallArgs(MInst, *this);
 245     else
 246       assert( 0 && "Non call/ret instr in CallRetInstrList" );
 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
 270
 271 // Checks if live range LR interferes with any node assigned or suggested to
 272 // be assigned the specified color
 273 //
 274 inline bool InterferesWithColor(const LiveRange& LR, unsigned color)
 275 {
 276   IGNode* lrNode = LR.getUserIGNode();
 277   for (unsigned n=0, NN = lrNode->getNumOfNeighbors(); n < NN; n++) {
 278     LiveRange *neighLR = lrNode->getAdjIGNode(n)->getParentLR();
 279     if (neighLR->hasColor() && neighLR->getColor() == color)
 280       return true;
 281     if (neighLR->hasSuggestedColor() && neighLR->getSuggestedColor() == color)
 282       return true;
 283   }
 284   return false;
 285 }
 286
 287 // Cannot coalesce if any of the following is true:
 288 // (1) Both LRs have suggested colors (should be "different suggested colors"?)
 289 // (2) Both LR1 and LR2 have colors and the colors are different
 290 //    (but if the colors are the same, it is definitely safe to coalesce)
 291 // (3) LR1 has color and LR2 interferes with any LR that has the same color
 292 // (4) LR2 has color and LR1 interferes with any LR that has the same color
 293 //
 294 inline bool InterfsPreventCoalescing(const LiveRange& LROfDef,
 295                                      const LiveRange& LROfUse)
 296 {
 297   // (4) if they have different suggested colors, cannot coalesce
 298   if (LROfDef.hasSuggestedColor() && LROfUse.hasSuggestedColor())
 299     return true;
 300
 301   // if neither has a color, nothing more to do.
 302   if (! LROfDef.hasColor() && ! LROfUse.hasColor())
 303     return false;
 304
 305   // (2, 3) if L1 has color...
 306   if (LROfDef.hasColor()) {
 307     if (LROfUse.hasColor())
 308       return (LROfUse.getColor() != LROfDef.getColor());
 309     return InterferesWithColor(LROfUse, LROfDef.getColor());
 310   }
 311
 312   // (4) else only LROfUse has a color: check if that could interfere
 313   return InterferesWithColor(LROfDef, LROfUse.getColor());
 314 }
 315
 316
 317 void LiveRangeInfo::coalesceLRs()
 318 {
 319   if(DEBUG_RA >= RA_DEBUG_LiveRanges)
 320     std::cerr << "\nCoalescing LRs ...\n";
 321
 322   MachineFunction &MF = MachineFunction::get(Meth);
 323   for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
 324     MachineBasicBlock &MBB = *BBI;
 325
 326     // iterate over all the machine instructions in BB
 327     for(MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII){
 328       const MachineInstr *MI = *MII;
 329
 330       if( DEBUG_RA >= RA_DEBUG_LiveRanges) {
 331         std::cerr << " *Iterating over machine instr ";
 332         MI->dump();
 333         std::cerr << "\n";
 334       }
 335
 336       // iterate over  MI operands to find defs
 337       for(MachineInstr::const_val_op_iterator DefI = MI->begin(),
 338             DefE = MI->end(); DefI != DefE; ++DefI) {
 339         if (DefI.isDefOnly() || DefI.isDefAndUse()) { // this operand is modified
 340           LiveRange *LROfDef = getLiveRangeForValue( *DefI );
 341           RegClass *RCOfDef = LROfDef->getRegClass();
 342
 343           MachineInstr::const_val_op_iterator UseI = MI->begin(),
 344             UseE = MI->end();
 345           for( ; UseI != UseE; ++UseI) { // for all uses
 346             LiveRange *LROfUse = getLiveRangeForValue( *UseI );
 347             if (!LROfUse) {             // if LR of use is not found
 348               //don't warn about labels
 349               if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges)
 350                 std::cerr << " !! Warning: No LR for use " << RAV(*UseI)<< "\n";
 351               continue;                 // ignore and continue
 352             }
 353
 354             if (LROfUse == LROfDef)     // nothing to merge if they are same
 355               continue;
 356
 357             if (MRI.getRegTypeForLR(LROfDef) ==
 358                 MRI.getRegTypeForLR(LROfUse)) {
 359               // If the two RegTypes are the same
 360               if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
 361
 362                 unsigned CombinedDegree =
 363                   LROfDef->getUserIGNode()->getNumOfNeighbors() +
 364                   LROfUse->getUserIGNode()->getNumOfNeighbors();
 365
 366                 if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) {
 367                   // get more precise estimate of combined degree
 368                   CombinedDegree = LROfDef->getUserIGNode()->
 369                     getCombinedDegree(LROfUse->getUserIGNode());
 370                 }
 371
 372                 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
 373                   // if both LRs do not have different pre-assigned colors
 374                   // and both LRs do not have suggested colors
 375                   if (! InterfsPreventCoalescing(*LROfDef, *LROfUse)) {
 376                     RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
 377                     unionAndUpdateLRs(LROfDef, LROfUse);
 378                   }
 379
 380                 } // if combined degree is less than # of regs
 381               } // if def and use do not interfere
 382             }// if reg classes are the same
 383           } // for all uses
 384         } // if def
 385       } // for all defs
 386     } // for all machine instructions
 387   } // for all BBs
 388
 389   if (DEBUG_RA >= RA_DEBUG_LiveRanges)
 390     std::cerr << "\nCoalescing Done!\n";
 391 }
 392
 393 /*--------------------------- Debug code for printing ---------------*/
 394
 395
 396 void LiveRangeInfo::printLiveRanges() {
 397   LiveRangeMapType::iterator HMI = LiveRangeMap.begin();   // hash map iterator
 398   std::cerr << "\nPrinting Live Ranges from Hash Map:\n";
 399   for( ; HMI != LiveRangeMap.end(); ++HMI) {
 400     if (HMI->first && HMI->second) {
 401       std::cerr << " Value* " << RAV(HMI->first) << "\t: ";
 402       if (IGNode* igNode = HMI->second->getUserIGNode())
 403         std::cerr << "LR# " << igNode->getIndex();
 404       else
 405         std::cerr << "LR# " << "<no-IGNode>";
 406       std::cerr << "\t:Values = "; printSet(*HMI->second); std::cerr << "\n";
 407     }
 408   }
 409 }