LiveIntervalAnalysis.cpp

  // dead intervals.
  std::vector<LiveInterval*> RetNewLIs;
  for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
    LiveInterval *LI = NewLIs[i];
    if (!LI->empty()) {
      LI->weight /= SlotIndex::NUM * getApproximateInstructionCount(*LI);
      if (!AddedKill.count(LI)) {
        LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
        SlotIndex LastUseIdx = LR->end.getBaseIndex();
        MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
        int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
        assert(UseIdx != -1);
        if (!LastUse->isRegTiedToDefOperand(UseIdx)) {
          LastUse->getOperand(UseIdx).setIsKill();
          vrm.addKillPoint(LI->reg, LastUseIdx);
        }
      }
      RetNewLIs.push_back(LI);
    }
  }

  handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
  normalizeSpillWeights(RetNewLIs);
  return RetNewLIs;
}

/// hasAllocatableSuperReg - Return true if the specified physical register has
/// any super register that's allocatable.
bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
  for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
    if (allocatableRegs_[*AS] && hasInterval(*AS))
      return true;
  return false;
}

/// getRepresentativeReg - Find the largest super register of the specified
/// physical register.
unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
  // Find the largest super-register that is allocatable. 
  unsigned BestReg = Reg;
  for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
    unsigned SuperReg = *AS;
    if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
      BestReg = SuperReg;
      break;
    }
  }
  return BestReg;
}

/// getNumConflictsWithPhysReg - Return the number of uses and defs of the
/// specified interval that conflicts with the specified physical register.
unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
                                                   unsigned PhysReg) const {
  unsigned NumConflicts = 0;
  const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
  for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
         E = mri_->reg_end(); I != E; ++I) {
    MachineOperand &O = I.getOperand();
    MachineInstr *MI = O.getParent();
    if (MI->isDebugValue())
      continue;
    SlotIndex Index = getInstructionIndex(MI);
    if (pli.liveAt(Index))
      ++NumConflicts;
  }
  return NumConflicts;
}

/// spillPhysRegAroundRegDefsUses - Spill the specified physical register
/// around all defs and uses of the specified interval. Return true if it
/// was able to cut its interval.
bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
                                            unsigned PhysReg, VirtRegMap &vrm) {
  unsigned SpillReg = getRepresentativeReg(PhysReg);

  for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
    // If there are registers which alias PhysReg, but which are not a
    // sub-register of the chosen representative super register. Assert
    // since we can't handle it yet.
    assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) ||
           tri_->isSuperRegister(*AS, SpillReg));

  bool Cut = false;
  SmallVector<unsigned, 4> PRegs;
  if (hasInterval(SpillReg))
    PRegs.push_back(SpillReg);
  else {
    SmallSet<unsigned, 4> Added;
    for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS)
      if (Added.insert(*AS) && hasInterval(*AS)) {
        PRegs.push_back(*AS);
        for (const unsigned* ASS = tri_->getSubRegisters(*AS); *ASS; ++ASS)
          Added.insert(*ASS);
      }
  }

  SmallPtrSet<MachineInstr*, 8> SeenMIs;
  for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
         E = mri_->reg_end(); I != E; ++I) {
    MachineOperand &O = I.getOperand();
    MachineInstr *MI = O.getParent();
    if (MI->isDebugValue() || SeenMIs.count(MI))
      continue;
    SeenMIs.insert(MI);
    SlotIndex Index = getInstructionIndex(MI);
    for (unsigned i = 0, e = PRegs.size(); i != e; ++i) {
      unsigned PReg = PRegs[i];
      LiveInterval &pli = getInterval(PReg);
      if (!pli.liveAt(Index))
        continue;
      vrm.addEmergencySpill(PReg, MI);
      SlotIndex StartIdx = Index.getLoadIndex();
      SlotIndex EndIdx = Index.getNextIndex().getBaseIndex();
      if (pli.isInOneLiveRange(StartIdx, EndIdx)) {
        pli.removeRange(StartIdx, EndIdx);
        Cut = true;
      } else {
        std::string msg;
        raw_string_ostream Msg(msg);
        Msg << "Ran out of registers during register allocation!";
        if (MI->isInlineAsm()) {
          Msg << "\nPlease check your inline asm statement for invalid "
              << "constraints:\n";
          MI->print(Msg, tm_);
        }
        report_fatal_error(Msg.str());
      }
      for (const unsigned* AS = tri_->getSubRegisters(PReg); *AS; ++AS) {
        if (!hasInterval(*AS))
          continue;
        LiveInterval &spli = getInterval(*AS);
        if (spli.liveAt(Index))
          spli.removeRange(Index.getLoadIndex(),
                           Index.getNextIndex().getBaseIndex());
      }
    }
  }
  return Cut;
}

LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
                                                  MachineInstr* startInst) {
  LiveInterval& Interval = getOrCreateInterval(reg);
  VNInfo* VN = Interval.getNextValue(
    SlotIndex(getInstructionIndex(startInst).getDefIndex()),
    startInst, true, getVNInfoAllocator());
  VN->setHasPHIKill(true);
  VN->kills.push_back(indexes_->getTerminatorGap(startInst->getParent()));
  LiveRange LR(
     SlotIndex(getInstructionIndex(startInst).getDefIndex()),
     getMBBEndIdx(startInst->getParent()), VN);
  Interval.addRange(LR);
  
  return LR;
}