LiveIntervalAnalysis.cpp

    typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair;
    bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const {
      if (LHS.first > RHS.first) return true;   // Deeper loops first
      return LHS.first == RHS.first &&
        LHS.second->getNumber() < RHS.second->getNumber();
    }
  };
}


void LiveIntervals::CopyCoallesceInMBB(MachineBasicBlock *MBB,
                                       std::vector<CopyRec> &TryAgain) {
  DEBUG(std::cerr << ((Value*)MBB->getBasicBlock())->getName() << ":\n");
  
  for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
       MII != E;) {
    MachineInstr *Inst = MII++;
    
    // If this isn't a copy, we can't join intervals.
    unsigned SrcReg, DstReg;
    if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg)) continue;
    
    if (!JoinCopy(Inst, SrcReg, DstReg))
      TryAgain.push_back(getCopyRec(Inst, SrcReg, DstReg));
  }
}


void LiveIntervals::joinIntervals() {
  DEBUG(std::cerr << "********** JOINING INTERVALS ***********\n");

  std::vector<CopyRec> TryAgainList;
  
  const LoopInfo &LI = getAnalysis<LoopInfo>();
  if (LI.begin() == LI.end()) {
    // If there are no loops in the function, join intervals in function order.
    for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
         I != E; ++I)
      CopyCoallesceInMBB(I, TryAgainList);
  } else {
    // Otherwise, join intervals in inner loops before other intervals.
    // Unfortunately we can't just iterate over loop hierarchy here because
    // there may be more MBB's than BB's.  Collect MBB's for sorting.
    std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs;
    for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
         I != E; ++I)
      MBBs.push_back(std::make_pair(LI.getLoopDepth(I->getBasicBlock()), I));

    // Sort by loop depth.
    std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare());

    // Finally, join intervals in loop nest order.
    for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
      CopyCoallesceInMBB(MBBs[i].second, TryAgainList);
  }

  // Joining intervals can allow other intervals to be joined.  Iteratively join
  // until we make no progress.
  bool ProgressMade = true;
  while (ProgressMade) {
    ProgressMade = false;
    
    for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) {
      CopyRec &TheCopy = TryAgainList[i];
      if (TheCopy.MI &&
          JoinCopy(TheCopy.MI, TheCopy.SrcReg, TheCopy.DstReg)) {
        TheCopy.MI = 0;   // Mark this one as done.
        ProgressMade = true;
      }
    }
  }
  
  DEBUG(std::cerr << "*** Register mapping ***\n");
  DEBUG(for (int i = 0, e = r2rMap_.size(); i != e; ++i)
          if (r2rMap_[i]) {
            std::cerr << "  reg " << i << " -> ";
            printRegName(r2rMap_[i]);
            std::cerr << "\n";
          });
}

/// Return true if the two specified registers belong to different register
/// classes.  The registers may be either phys or virt regs.
bool LiveIntervals::differingRegisterClasses(unsigned RegA,
                                             unsigned RegB) const {

  // Get the register classes for the first reg.
  if (MRegisterInfo::isPhysicalRegister(RegA)) {
    assert(MRegisterInfo::isVirtualRegister(RegB) &&
           "Shouldn't consider two physregs!");
    return !mf_->getSSARegMap()->getRegClass(RegB)->contains(RegA);
  }

  // Compare against the regclass for the second reg.
  const TargetRegisterClass *RegClass = mf_->getSSARegMap()->getRegClass(RegA);
  if (MRegisterInfo::isVirtualRegister(RegB))
    return RegClass != mf_->getSSARegMap()->getRegClass(RegB);
  else
    return !RegClass->contains(RegB);
}

LiveInterval LiveIntervals::createInterval(unsigned reg) {
  float Weight = MRegisterInfo::isPhysicalRegister(reg) ?
                       (float)HUGE_VAL : 0.0F;
  return LiveInterval(reg, Weight);
}